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.

Examples

Input

3
1
2
1

Output

2

Input

5
3
1
4
1
5

Output

0

Input

8
4
4
4
1
1
1
2
2

Output

24

Input

6
1
1
6
2
2
2

Output

0

见题面

见题面