Problem Description

On a beautiful morning, Little S and his friend Little A were counting trees in a small forest. Inspired by the sight of the trees, Little S came up with a problem.

Now there are \( n \) points, each with a weight \( v_i \).

Little S wants Little A to select some points to form a set, denoted as \( S = \{d_1, d_2, \dots, d_m\} \) where \( 1 \leq m \leq n \).

Little A must ensure that these points can form a tree, and the degree of \( d_i \) is \( v_{d_i} \) for \( i \in [1, m] \).

• The degree of a node is the number of adjacent nodes.

Little S asks Little A how many valid schemes there are.

Since the number of schemes can be very large, please take the result modulo \( 998244353 \).

Input Format

The first line contains an integer \( n \).

The second line contains \( n \) integers \( v_1, v_2, \dots, v_n \).

Output Format

Output a single integer, representing the number of schemes.

Sample Input and Output

Input Sample #1

3
1 1 1

Output Sample #1

3

Input Sample #2

5
1 2 1 3 1

Output Sample #2

8

Input Sample #3

8
1 2 1 2 4 1 3 1

Output Sample #3

44

Input Sample #4

50
8 1 10 2 2 1 2 1 1 2 5 1 11 6 13 13 10 4 1 13 11 2 2 11 13 10 1 1 4 3 4 2 15 2 2 1 1 2 1 7 14 2 2 4 13 2 7 5 6 10

Output Sample #4

176873472

Notes

Sample Explanation

• For Sample 1, any two nodes can be chosen from the three, resulting in \( C^2_3 = 3 \).

• For Sample 2, as shown in the figure, there are 8 ways to choose nodes.

Data Range and Constraints

This problem uses batched testing.

For \( 100\% \) of the data, \( 2 \leq n \leq 5 \times 10^5 \), \( 1 \leq v_i \leq n \).

In Subtask 7, "data is random" means: For each \( v_i \), there is a \( \frac{1}{3} \) chance it is 1, and a \( \frac{2}{3} \) chance it is a number chosen uniformly at random from \( [2, n] \).

For the first 4 Subtasks, the time limit is 1 second.

For the 5th Subtask, the time limit is 3 seconds.

For the last 3 Subtasks, the time limit is 6 seconds.

For all test cases, the space limit is 256 MB.

见题面 Input 部分

见题面 Output 部分