Problem Description

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 transformed into the sequence \( A_1, A_2, ..., A_N \) by performing the following operation any number of times, 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 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( A_1 \) \( : \) \( A_N \)

Output Format

Output the number of such sequences modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

3
1
2
1

Sample Output #1

2

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

Notes/Hints

Constraints

• \( 1 \leq N \leq 3 \times 10^5 \)
• \( 1 \leq A_i \leq N \)
• All inputs are integers.

Sample Explanation 1

\( (2, 3, 1), (3, 2, 1) \) satisfy the condition.

见题面 Input 部分

见题面 Output 部分