/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力してください。
入力例 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
Score : 700 points
Problem Statement
You are given a multiset of integers with N elements: A=\lbrace A_1,A_2,...,A_N \rbrace. It is guaranteed that every element of A is between 1 and M (inclusive).
Let us repeat the following operation K times.
- Choose an integer between 1 and M (inclusive) and add it to A. Then, delete the X-th smallest value in A.
Here, the X-th smallest value in A is the X-th value from the front in the sequence of the elements of A sorted in non-decreasing order.
There are M^K ways to choose an integer K times between 1 and M. Assume that, for each of these ways, we have found the sum of the elements of A after the operations with the corresponding choices. Find the sum, modulo 998244353, of the M^K values computed.
Constraints
- 1 \le N,M,K \le 2000
- 1 \le X \le N+1
- 1 \le A_i \le M
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K X A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
2 4 2 1 1 3
Sample Output 1
99
We start with A=\{1,3\}. Here is an example of how we do the operations.
-
Add 4 to A, making A=\{1,3,4\}. Then, delete the 1-st smallest value, making A=\{3,4\}.
-
Add 3 to A, making A=\{3,3,4\}. Then, delete the 1-st smallest value, making A=\{3,4\}.
In this case, the sum of the elements of A after the operations is 3+4=7.
Sample Input 2
5 9 6 3 3 7 1 9 9
Sample Output 2
15411789