Circular

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

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format:

N A_1 : A_N

outputFormat

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

样例

3
1
2
1

2