問題文

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

制約

• $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$ で出力せよ。

入力例 1

3 5 2
2 0 4

出力例 1

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

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