题目描述

给定一个包含 $N$ 个元素的整数多重集合 $A=\lbrace\ A_1,A_2,\ldots,A_N\ \rbrace$。保证 $A$ 的所有元素都在 $1$ 到 $M$ 之间。

以下操作重复 $K$ 次：

• 选择一个 $1$ 到 $M$ 之间的整数，将其加入 $A$。然后，从 $A$ 中删除第 $X$ 小的元素（即将 $A$ 按非降序排列后，从前往后数第 $X$ 个元素）。

选择 $K$ 次要加入 $A$ 的数的方法共有 $M^K$ 种。对于每一种方法，操作结束后 $A$ 的元素总和是多少？请计算所有 $M^K$ 种情况的 $A$ 的元素总和之和，并对 $998244353$ 取模。

输入格式

输入为一行，包含 $N$、$M$、$K$、$X$ 以及 $A_1$、$A_2$、$\dots$、$A_N$，用空格分隔。

输出格式

输出答案。

样例 1

输入

2 4 2 1
1 3

输出

99

样例 2

输入

5 9 6 3
3 7 1 9 9

输出

15411789

说明/提示

限制条件

• $1\leq N,M,K\leq 2000$
• $1\leq X\leq N+1$
• $1\leq A_i\leq M$
• 输入均为整数。

样例解释 1

初始时 $A=\{1,3\}$。操作的例子如下：

• 向 $A$ 中加入 $4$，此时 $A=\{1,3,4\}$。删除 $A$ 中第 $1$ 小的元素，$A=\{3,4\}$。
• 向 $A$ 中加入 $3$，此时 $A=\{1,3,3\}$。删除 $A$ 中第 $1$ 小的元素，$A=\{3,3\}$。

在这种情况下，操作结束后 $A$ 的元素总和为 $3+4=7$。

由 ChatGPT 4.1 翻译