分数: 500 点
问题陈述
我们有一个长度为 N 由之间的整数组成 0 和 M,包括: A=(A_1,A_2,\dots,A_N).
Snuke 将按顺序执行以下操作 1 和 2。
- 对于每个 i 这样 A_i=0,独立选择一个均匀随机整数 1 和 M,包含在内,并替换 A_i 与该整数。
- 排序 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将取代 A_2 之间的整数 1 和 5。让 x 是这个整数。
- If x=1 or 2,我们将有 A_2=2 两次操作后。
- If x=3,我们将有 A_2=3 两次操作后。
- If x=4 or 5,我们将有 A_2=4 两次操作后。
因此,预期值 A_2 is \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