Problem Description

Snuke came up with the following problem:

Given a sequence $ d $ of length $ N $. Calculate the number of undirected graphs with $ N $ vertices labeled $ 1, 2, ..., N $ that satisfy the following conditions modulo $ 10^{9} + 7 $.

• The graph is simple and connected.
• The degree of vertex $ i $ is $ d_i $.

**For $2 \leq N, 1 \leq d_i \leq N-1, \Sigma d_i = 2(N-1)**,$ \frac{(N-2)!}{(d_{1} -1)!(d_{2} - 1)!\ ...\ (d_{N}-1)!} $.

Snuke is curious about what happens for $3 \leq N, 1 \leq d_i \leq N-1, \Sigma d_i = 2N$. Solve this problem on behalf of Snuke.

Input Format

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

$ N $ $ d_1 $ $ d_2 $ $ ... $ $ d_{N} $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

5
1 2 2 3 2

Sample Output #1

6

Sample Input #2

16
2 1 3 1 2 1 4 1 1 2 1 1 3 2 4 3

Sample Output #2

555275958

Notes/Hints

Constraints

• $3 \leq N \leq 300$
• $1 \leq d_i \leq N-1$
• $\Sigma d_i = 2N$

Partial Points

• For a dataset worth 200 points, $N \leq 5$ holds.
• For another dataset worth 200 points, $N \leq 18$ holds.
• For another dataset worth 300 points, $N \leq 50$ holds.

Sample Explanation 1

• There are 6 possible graphs as shown in the following figure:

Sample Explanation 2

• Calculate the remainder divided by $ 10^{9} + 7 $.

见题面 Input 部分

见题面 Output 部分