Problem Description

There are $n$ wooden blocks arranged in a row, numbered from $1$ to $n$ from left to right.

You have $k$ types of paint, and the $i$-th type of paint is sufficient to color $c_i$ blocks.

All the paint is exactly enough to color all the blocks, i.e., $\sum_{i=1}^k c_i = n$.

Since adjacent blocks painted with the same color look unappealing, you want to count the coloring schemes where no two adjacent blocks have the same color.

As the answer may be very large, output the result modulo $10^9 + 7$.

Input Format

The first line contains an integer $k$, representing the number of colors.

The second line contains $k$ integers $c_1, c_2, \dots, c_k$, representing the number of blocks each color can paint.

Output Format

A single line containing an integer, representing the answer modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

10

Sample Input #2

5
2 2 2 2 2

Sample Output #2

39480

Sample Input #3

10
1 1 2 2 3 3 4 4 5 5

Sample Output #3

85937576

Notes

• For $50\%$ of the data, $1 \leq k \leq 5$, $1 \leq c_i \leq 3$;
• For $100\%$ of the data, $1 \leq k \leq 15$, $1 \leq c_i \leq 5$.

见题面 Input 部分

见题面 Output 部分