题目描述

要素数が $N$ の整数の多重集合 $A=\lbrace\ A_1,A_2,...,A_N\ \rbrace$ が与えられます。$A$ の要素は全て $1$ 以上 $M$ 以下であることが保証されています。

以下の操作を $K$ 回繰り返します。

• $1$ 以上 $M$ 以下の整数を選び、$A$ に追加する。その後、$A$ の中で $X$ 番目に小さい値を $1$ 個削除する。

$A$ の中で $X$ 番目に小さい値とは、$A$ の要素を単調非減少になるように一列に並べたとき、先頭から $X$ 番目にくる値のことです。

$1$ 以上 $M$ 以下の値を $K$ 回選ぶ方法は $M^K$ 通りありますが、その全てに対して操作終了後の $A$ の要素の総和を求めたとします。これらの $M^K$ 個の値の総和を $998244353$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $M$ $K$ $X$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

答えを出力してください。

题目大意

给定 $n,m,k,x$，给定了一个有 $n$ 个元素的可重集合 $a_i\in [1,m]$，会进行 $k$ 次如下操作：选择一个数 $y\in[1,m]$ 加到 $a$ 中，并把 $a$ 中第 $x$ 小的元素删除。

有 $m^k$ 种情况，对于每种情况的价值定义为最后 $a$ 集合的和，对于所有情况价值求和。

• $1\le n,m,k\le 2000$，$1\le x\le n+1$，$1\le a_i\le m$

2 4 2 1
1 3

99

5 9 6 3
3 7 1 9 9

15411789

提示

制約

• $1\ \le\ N,M,K\ \le\ 2000$
• $1\ \le\ X\ \le\ N+1$
• $1\ \le\ A_i\ \le\ M$
• 入力は全て整数である。

Sample Explanation 1

初め $A=\{1,3\}$ です。操作の例としては以下のようなものが考えられます。 - $A$ に $4$ を追加する。$A=\{1,3,4\}$ となる。$A$ の $1$ 番目に小さい値を削除する。$A=\{3,4\}$ となる。 - $A$ に $3$ を追加する。$A=\{3,3,4\}$ となる。$A$ の $1$ 番目に小さい値を削除する。$A=\{3,4\}$ となる。 この場合、操作後の $A$ の要素の総和は $3+4=7$ となります。