Problem Statement

You are given a sequence of N non-negative integers: $D=(D_1, D_2, \dots, D_N)$.
Find the number of labeled trees with N vertices numbered 1 to N that satisfy the following condition, modulo 998244353.

• There is a way to direct the N-1 edges so that the outdegree of each vertex i\ $(1\leq i \leq N)$ is D_i.

Input

The input is given from Standard Input in the following format:
N
$D_1 D_2 \dots D_N$

Output

Print the answer.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq D_i \leq N-1$
• $\sum_{i=1}^{N} D_i = N-1$
• All values in the input are integers.

Sample Input 1

4
0 1 0 2

Sample Output 1

5

Below are the five trees that satisfy the condition, directed in a desired way.

Sample Input 2

5
0 1 1 1 1

Sample Output 2

125

Sample Input 3

15
0 0 0 0 0 0 0 1 1 1 1 1 2 3 4

Sample Output 3

63282877

见题面 Input 部分

见题面 Output 部分