E - Kth Number Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

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

「期待値を \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

Score : 500 points

Problem Statement

We have a sequence of length N consisting of integers between 0 and M, inclusive: A=(A_1,A_2,\dots,A_N).

Snuke will perform the following operations 1 and 2 in order.

  1. For each i such that A_i=0, independently choose a uniform random integer between 1 and M, inclusive, and replace A_i with that integer.
  2. Sort A in ascending order.

Print the expected value of A_K after the two operations, modulo 998244353.

How to print a number modulo 998244353? It can be proved that the sought expected value is always rational. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, it can be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print this R.

Constraints

  • 1\leq K \leq N \leq 2000
  • 1\leq M \leq 2000
  • 0\leq A_i \leq M
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M K
A_1 A_2 \dots A_N

Output

Print the expected value of A_K after the two operations, modulo 998244353.

Sample Input 1

3 5 2
2 0 4

Sample Output 1

3

In the operation 1, Snuke will replace A_2 with an integer between 1 and 5. Let x be this integer.

  • If x=1 or 2, we will have A_2=2 after the two operations.
  • If x=3, we will have A_2=3 after the two operations.
  • If x=4 or 5, we will have A_2=4 after the two operations.

Thus, the expected value of A_2 is \frac{2+2+3+4+4}{5}=3.

Sample Input 2

2 3 1
0 0

Sample Output 2

221832080

The expected value is \frac{14}{9}.

Sample Input 3

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

Sample Output 3

617586310