分数: 900 点
问题陈述
给你一系列 N 整数: A_1,A_2,...,A_N.
求排列数 p_1,p_2,...,p_N of 1,2,...,N 可以通过执行以下操作若干次(可能为零)变为 A_1,A_2,...,A_N ,模 998244353:
- 对于每个 1\leq i\leq N,让 q_i=min(p_{i-1},p_{i}),其中 p_0=p_N。将序列 p 替换为序列 q.
约束
- 1 \leq N \leq 3 × 10^5
- 1 \leq A_i \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 : A_N
输出
。打印满足条件的序列的数量,模 998244353.
示例输入 1
3 1 2 1
示例输出 1
2
(2,3,1) 和 (3,2,1) 满足条件。
示例输入 2
5 3 1 4 1 5
示例输出 2
0
示例输入 3
8 4 4 4 1 1 1 2 2
示例输出 3
24
示例输入 4
6 1 1 6 2 2 2
示例输出 4
0