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