Description

There are $n$ vertices, and each vertex has a weight $v_i$.

Little $\mathrm{S}$ wants Little $\mathrm{A}$ to choose some vertices to form a set. Let the set be $S=\{d_1,d_2,\dots,d_m\}(1\leq m\leq n)$.

Of course, Little $\mathrm{A}$ also needs to ensure that these vertices can form a tree, and the degree of $d_i$ is $v_{d_i}(i\in[1,m])$.

• Degree of a vertex: the number of vertices adjacent to it.

Little $\mathrm{S}$ asks Little $\mathrm{A}$ how many ways there are that satisfy the conditions.

Little $\mathrm{A}$ knows he definitely cannot solve this problem, so he asks you for help.

Since the number of ways may be very large, output it 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 one integer in one line, representing the number of valid ways.

3
1 1 1

3

5
1 2 1 3 1

8

8
1 2 1 2 4 1 3 1

44

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 

176873472

Hint

Sample Explanation

• For sample $1$, it is enough to choose any two vertices among the three vertices. The answer is $C^{2}_{3}=3$.

• For sample $2$, as shown in the figure, there are $8$ ways to choose vertices.

Constraints and Notes

This problem uses bundled testdata.

For $100\%$ of the testdata, $2 \leq n \leq 5 \times 10^5$ and $\ 1 \leq v_i \leq n$.

In $\mathrm{Subtask\ 7}$, “random testdata” means: for every $v_i$, it equals $1$ with probability $\frac{1}{3}$, and with probability $\frac{2}{3}$ it is chosen uniformly at random from $[2,n]$.

For the first $4$ $\mathrm{Subtask}$s, the time limit is $1\mathrm{s}$.

For the $5$th $\mathrm{Subtask}$, the time limit is $3\mathrm{s}$.

For the last $3$ $\mathrm{Subtask}$s, the time limit is $6\mathrm{s}$.

For all test points, the memory limit is $256\mathrm{MB}$.

Translated by ChatGPT 5