Description

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

You have $k$ colors of paint, and the $i$-th color is enough to paint $c_i$ blocks.

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

Since it looks bad if two adjacent blocks have the same color, you want to count the number of colorings in which any two adjacent blocks have different colors.

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

Input Format

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

The second line contains $k$ integers $c_1, c_2, \dots, c_k$, where $c_i$ is the number of blocks that can be painted with the $i$-th color.

Output Format

Output a single integer, the answer modulo $10^9+7$.

3
1 2 3

10

5
2 2 2 2 2

39480

10
1 1 2 2 3 3 4 4 5 5

85937576

Hint

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

Translated by ChatGPT 5