题目描述

给定一个包含$N$个元素的多重集合：$A=\\lbrace A_1,A_2,...,A_N \\rbrace$。保证$A$中的每个元素都在$1$和$M$之间（包括$1$和$M$）。

我们将重复进行以下操作$K$次。

• 从$1$到$M$（包括$1$和$M$）中选择一个整数，并将其添加到$A$中。然后，删除$A$中第$X$小的值。

这里，$A$中第$X$小的值是$A$中元素按非递减顺序排列后，从前往后的第$X$个值。

在选择出的整数方式中，有$M^K$种方法进行$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\\}$开始。以下是操作的一个示例。

• 将$4$添加到$A$中，使得$A=\\{1,3,4\\}$。然后，删除第$1$个最小值，使得$A=\\{3,4\\}$。

• 将$3$添加到$A$中，使得$A=\\{3,3,4\\}$。然后，删除第$1$个最小值，使得$A=\\{3,4\\}$。

在这种情况下，操作后$A$中元素的和为$3+4=7$。

示例输入2

5 9 6 3
3 7 1 9 9

示例输出2

15411789