题目描述

我们有一个长度为$N$的序列，由介于$0$和$M$之间（包括$0$和$M$）的整数组成：$A=(A_1,A_2,\dots,A_N)$。

Snuke将按照以下操作1和2的顺序执行。

1. 对于每个$i$使得$A_i=0$，独立地选择介于$1$和$M$之间（包括$1$和$M$）的均匀随机整数，并用该整数替换$A_i$。
2. 按升序对$A$进行排序。

在进行两次操作后，打印出$A_K$的期望值（对$998244353$取模）。

如何打印出数模$998244353$的值？可以证明所求的期望值始终是有理数。此外，在这个问题的约束条件下，当该值表示为$\\frac{P}{Q}$，其中$P$和$Q$是互质的整数时，可以证明存在唯一的整数$R$，满足$R \\times Q \\equiv P\\pmod{998244353}$且$0 \\leq R \\lt 998244353$。输出这个$R$。

约束条件

• $1\\leq K \\leq N \\leq 2000$
• $1\\leq M \\leq 2000$
• $0\\leq A_i \\leq M$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出

在进行两次操作后，打印出$A_K$的期望值（对$998244353$取模）。

示例输入 1

3 5 2
2 0 4

示例输出 1

3

在操作1中，Snuke将用介于$1$和$5$之间的整数替换$A_2$。设该整数为$x$。

• 如果$x=1$或$2$，两次操作后我们将有$A_2=2$。
• 如果$x=3$，两次操作后我们将有$A_2=3$。
• 如果$x=4$或$5$，两次操作后我们将有$A_2=4$。

因此，$A_2$的期望值是$\\frac{2+2+3+4+4}{5}=3$。

示例输入 2

2 3 1
0 0

示例输出 2

221832080

期望值是$\\frac{14}{9}$。

示例输入 3

10 20 7
6 5 0 2 0 0 0 15 0 0

示例输出 3

617586310