Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
整数 N 個からなる列 A_1,A_2,...,A_N が与えられます。
1,2,...,N の並び替え p_1,p_2,...,p_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
Score : 900 points
Problem Statement
You are given a sequence of N integers: A_1,A_2,...,A_N.
Find the number of permutations p_1,p_2,...,p_N of 1,2,...,N that can be changed to A_1,A_2,...,A_N by performing the following operation some number of times (possibly zero), modulo 998244353:
- For each 1\leq i\leq N, let q_i=min(p_{i-1},p_{i}), where p_0=p_N. Replace the sequence p with the sequence q.
Constraints
- 1 \leq N \leq 3 × 10^5
- 1 \leq A_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 : A_N
Output
Print the number of the sequences that satisfy the condition, modulo 998244353.
Sample Input 1
3 1 2 1
Sample Output 1
2
(2,3,1) and (3,2,1) satisfy the condition.
Sample Input 2
5 3 1 4 1 5
Sample Output 2
0
Sample Input 3
8 4 4 4 1 1 1 2 2
Sample Output 3
24
Sample Input 4
6 1 1 6 2 2 2
Sample Output 4
0