C - Roughly Sorted Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

すぬけくんは，(1,\ 2,\ ...\ N) の順列 P=(P_1,P_2,\cdots,P_N) と整数 K をもらいました． そこですぬけくんは，P の隣接する二項をswapすることを繰り返して，以下の条件が満たされるようにしました．

  • それぞれの 1 \leq i \leq N について， 1 \leq j< i, P_j>P_i を満たす j が高々 K 個である．

ここで，すぬけくんは最小の操作回数でこの条件を達成しました．

すべての操作が終わったあと，すぬけくんは元の順列を忘れてしまいました． 操作後の順列 P' が与えられるので，元の順列 P としてあり得るものが何通りあるかを 998244353 で割った余りを求めてください．

制約

  • 2 \leq N \leq 5000
  • 1 \leq K \leq N-1
  • 1 \leq P'_i \leq N
  • P'_i \neq P'_j (i \neq j)
  • それぞれの 1 \leq i \leq N について， 1 \leq j< i, P'_j>P'_i を満たす j が高々 K 個である
  • 入力される値はすべて整数である

入力

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

N K
P'_1 P'_2 \cdots P'_N

出力

答えを出力せよ．

入力例 1

3 1
3 1 2

出力例 1

2

P として考えられるのは以下の 2 通りです．

  • P=(3,1,2): 最小の操作回数は 0 回です．操作後の順列は P' に一致します．
  • P=(3,2,1): 最小の操作回数は 1 回です．P_2 と P_3 をswapすることで，P=(3,1,2) となり，これは条件を満たします．操作後の順列は P' に一致します．

入力例 2

4 3
4 3 2 1

出力例 2

1

入力例 3

5 2
4 2 1 5 3

出力例 3

3

Score : 800 points

Problem Statement

Snuke received a permutation P=(P_1,P_2,\cdots,P_N) of (1,\ 2,\ ...\ N) and an integer K. He did some number of swaps of two adjacent elements in P so that the following condition would be satisfied.

  • For each 1 \leq i \leq N, there are at most K indices j such that 1 \leq j< i and P_j>P_i.

Here, he did the minimum number of swaps needed to achieve this condition.

Afterward, he has forgotten the original permutation he received. Given the permutation P' after the swaps, find the number, modulo 998244353, of permutations that the original permutation P could be.

Constraints

  • 2 \leq N \leq 5000
  • 1 \leq K \leq N-1
  • 1 \leq P'_i \leq N
  • P'_i \neq P'_j (i \neq j)
  • For each 1 \leq i \leq N, there is at most K indices j such that 1 \leq j< i and P'_j>P'_i.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P'_1 P'_2 \cdots P'_N

Output

Print the answer.

Sample Input 1

3 1
3 1 2

Sample Output 1

2

P could be one of the following two permutations.

  • P=(3,1,2): The minimum number of swaps needed is 0. After zero swaps, the permutation is equal to P'.
  • P=(3,2,1): The minimum number of swaps needed is 1: swapping P_2 and P_3 results in P=(3,1,2), which satisfies the condition and is equal to P'.

Sample Input 2

4 3
4 3 2 1

Sample Output 2

1

Sample Input 3

5 2
4 2 1 5 3

Sample Output 3

3