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.

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.

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.

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

见题面 Input 部分

见题面 Output 部分