AT_abc295_e [ABC295E] Kth Number

[problemUrl]: https://atcoder.jp/contests/abc295/tasks/abc295_e $ 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 $ で出力せよ。

### 制約 - $ 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} $ です。