第 K 个数

题目描述

我们有一个长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$，其中每个元素都是 $0$ 到 $M$ 之间的整数（含两端）。

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

1. 对每个满足 $A_i=0$ 的 $i$，独立地从 $1$ 到 $M$ 中等概率随机选择一个整数，并用该整数替换 $A_i$。
2. 将 $A$ 按升序排序。

请输出这两步操作后 $A_K$ 的期望值对 $998244353$ 取模的结果。

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

输入格式

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

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

输出格式

输出两步操作后 $A_K$ 的期望值对 $998244353$ 取模的结果。

样例

3 5 2
2 0 4

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 3 1
0 0

221832080

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

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

617586310

数据范围

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