AT_arc139_d [ARC139D] Priority Queue 2

[problemUrl]: https://atcoder.jp/contests/arc139/tasks/arc139_d 要素数が $ 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 $

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

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