题目描述

$0$ 以上 $M$ 以下の整数からなる長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ があります。

今からすぬけくんが以下の操作 1, 2 を順に行います。

1. $A_i=0$ を満たすそれぞれの $i$ について、$1$ 以上 $M$ 以下の整数を独立かつ一様ランダムに選び、$A_i$ をその整数で置き換える。
2. $A$ を昇順に並び替える。

すぬけくんが操作 1, 2 を行ったあとの $A_K$ の期待値を $\text{mod\ }\ 998244353$ で出力してください。

「期待値を $\text{mod\ }\ 998244353$ で出力」とは 求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P$, $Q$ を用いて $\frac{P}{Q}$ と表したとき、 $R\ \times\ Q\ \equiv\ P\pmod{998244353}$ かつ $0\ \leq\ R\ \lt\ 998244353$ を満たす整数 $R$ がただ $1$ つ存在することが証明できます。この $R$ を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

すぬけくんが操作 1, 2 を行ったあとの $A_K$ の期待値を $\text{mod\ }\ 998244353$ で出力せよ。

题目大意

给定长度为 $n$ 的数列 $a$ 与 $m$，$k$。接下来，$a$ 中所有为 $0$ 的数将被等概率地替换为 $[1,m]$ 中的任意一个整数。接着将数列 $a$ 从小到大排序。请你求出 $a_k$ 的期望值，结果对 $998244353$ 取模。

$1\le k\le n\le2000$，$1\le m\le 2000$。

3 5 2
2 0 4

3

2 3 1
0 0

221832080

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$
• 入力は全て整数

Sample Explanation 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$ です。

Sample Explanation 2

期待値は $\frac{14}{9}$ です。