分数: 550 点
问题陈述
给你正整数 N, M,以及一个序列 A = (A_1, A_2, \dots, A_N) 长度 N,每个元素是介于 1 和 N,包括在内。
求模数 998244353,序列 x = (x_1, x_2, \dots, x_N) 长度 N,每个元素是介于 1 和 M,包含在内,满足以下条件:
- x_i \leq x_{A_i} 对于每个 i (1 \leq i \leq N).
约束
- 1 \leq N, M \leq 2025
- 1 \leq A_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
3 3 2 1 1
示例输出 1
6
序列 x=(1,1,1),(2,2,1),(2,2,2),(3,3,1),(3,3,2),(3,3,3) 满足条件。
示例输入 2
4 9 1 1 1 1
示例输出 2
2025
示例输入 3
10 5 9 4 5 5 4 2 1 5 7 2
示例输出 3
10010