AT_abc295_e [ABC295E] Kth Number

有一个长度为 $N$ 的数列 $A=(A_1,A_2,\dots,A_N)$，其中每个元素都是 $0$ 到 $M$ 之间的整数。 现在，すぬけくん将依次进行以下两个操作： 1. 对于所有满足 $A_i=0$ 的 $i$，独立且等概率地选择一个 $1$ 到 $M$ 之间的整数，将 $A_i$ 替换为该整数。 2. 将数列 $A$ 按升序排序。 请输出すぬけくん完成操作 1 和 2 后 $A_K$ 的期望值，结果对 $998244353$ 取模。 “对 $998244353$ 取模输出期望值” 的意思是：可以证明，所求期望值一定是有理数。在本题的约束下，设其为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 互质。则存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

输入按以下格式从标准输入读入。 > $N$ $M$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

请输出すぬけくん完成操作 1 和 2 后 $A_K$ 的期望值，对 $998244353$ 取模。

## 约束 - $1\leq K\leq N\leq 2000$ - $1\leq M\leq 2000$ - $0\leq A_i\leq M$ - 输入均为整数 ## 样例解释 1 すぬけくん在操作 1 中将 $A_2$ 替换为 $1$ 到 $5$ 之间的整数。设该整数为 $x$，则： - 当 $x=1,2$ 时，操作 1 和 2 后 $A_2=2$。 - 当 $x=3$ 时，操作 1 和 2 后 $A_2=3$。 - 当 $x=4,5$ 时，操作 1 和 2 后 $A_2=4$。 因此，$A_2$ 的期望值为 $\frac{2+2+3+4+4}{5}=3$。 ## 样例解释 2 期望值为 $\frac{14}{9}$。 由 ChatGPT 4.1 翻译