G - Increasing K Times Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ N の整数列 A = (A_1, \dots, A_N) が与えられます。

(1, 2, \dots, N) を並べ替えて得られる列 P = (P_1, \dots, P_N) であって、次の条件を満たすものの総数を 998244353 で割った余りを求めてください。

  • A_{P_i} \lt A_{P_{i + 1}} となるような 1 以上 N-1 以下の整数 i がちょうど K 個存在する。

制約

  • 2 \leq N \leq 5000
  • 0 \leq K \leq N - 1
  • 1 \leq A_i \leq N \, (1 \leq i \leq N)
  • 入力は全て整数

入力

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

N K
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

4 2
1 1 2 2

出力例 1

4

P = (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3) の 4 通りが条件を満たします。

入力例 2

10 3
3 1 4 1 5 9 2 6 5 3

出力例 2

697112

Score : 600 points

Problem Statement

You are given an integer sequence A = (A_1, \dots, A_N) of length N.

Find the number, modulo 998244353, of permutations P = (P_1, \dots, P_N) of (1, 2, \dots, N) such that:

  • there exist exactly K integers i between 1 and (N-1) (inclusive) such that A_{P_i} \lt A_{P_{i + 1}}.

Constraints

  • 2 \leq N \leq 5000
  • 0 \leq K \leq N - 1
  • 1 \leq A_i \leq N \, (1 \leq i \leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

4 2
1 1 2 2

Sample Output 1

4

Four permutations satisfy the condition: P = (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3).

Sample Input 2

10 3
3 1 4 1 5 9 2 6 5 3

Sample Output 2

697112