配点 : $700$ 点

問題文

要素数が $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$ で割ったあまりを求めてください。

制約

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

入力

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

$N$ $M$ $K$ $X$

$A_1$ $A_2$ $\dots$ $A_N$

出力

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

2 4 2 1
1 3

99

初め $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$ となります。

5 9 6 3
3 7 1 9 9

15411789