問題文

要素数が $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$

出力

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

入力例 1

2 4 2 1
1 3

出力例 1

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

入力例 2

5 9 6 3
3 7 1 9 9

出力例 2

15411789