分数: 600 点
问题陈述
给你一个整数序列 A = (A_1, \dots, A_N) 长度 N.
求模数 998244353,排列 P = (P_1, \dots, P_N) of (1, 2, \dots, N) 这样:
- 完全存在 K 整数 i 之间 1 和 (N-1) (含)使得 A_{P_i} \lt A_{P_{i + 1}}.
约束
- 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).
示例输入 2
10 3 3 1 4 1 5 9 2 6 5 3
示例输出 2
697112