配点 : $500$ 点

問題文

$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$ で出力してください。

制約

• $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$

出力

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

3 5 2
2 0 4

3

すぬけくんは操作 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 3 1
0 0

221832080

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

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

617586310