分数: 700 点
问题陈述
给你一个正整数 N 和一系列 M 非负整数 A = (A_{1}, A_{2}, \dots, A_{M}).
这里,所有元素 A 是之间不同的整数 0 和 N-1,包括在内。
求模数 998244353,排列 P of (0, 1, \dots, N-1) 满足以下条件。
- 初始化序列后 B = (B_{1}, B_{2}, \dots, B_{N}) to P,可以使 B = A 通过重复以下操作一定次数:
- 选择 l 和 r 这样 1 \leq l \leq r \leq |B|,如果 \mathrm{mex}(\{B_{l}, B_{l+1}, \dots, B_{r}\}) 包含在 B,将其从 B.
什么是 \mathrm{mex}(X)?
对于有限集 X 非负整数, \mathrm{mex}(X) 被定义为不在其中的最小非负整数 X.约束
- 1 \leq M \leq N \leq 500
- 0 \leq A_{i} < N
- 的所有元素 A 是不同的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
A_{1} A_{2} \cdots A_{M}
输出
打印答案。
示例输入 1
4 2 1 3
示例输出 1
8
初始化后 B = (2, 1, 0, 3),可以使 B = A 使用以下步骤:
- 选择 (l, r) = (2, 4),删除 \mathrm{mex}(\{1, 0, 3\}) = 2 来自 B, 制作 B = (1, 0, 3).
- 选择 (l, r) = (3, 3),删除 \mathrm{mex}(\{3\}) = 0 来自 B, 制作 B = (1, 3).
因此, P = (2, 1, 0, 3) 满足条件。
有八种排列 P 满足条件,包括以上,所以打印 8.
示例输入 2
4 4 0 3 2 1
示例输出 2
1
仅 P = (0, 3, 2, 1) 满足条件。
示例输入 3
16 7 9 2 4 0 1 6 7
示例输出 3
3520
示例输入 4
92 4 1 67 16 7
示例输出 4
726870122
求计数模数 998244353.