Paint the Wooden Blocks

You are given a row of $n$ wooden blocks numbered from $1$ to $n$. You also have $k$ types of paint. For the $i$-th type of paint, you have exactly $c_i$ units available, and ( \sum_{i=1}^{k}c_i = n ), meaning that the paint is just enough to cover all the blocks. You need to paint all the blocks so that any two adjacent blocks have different colors. Count the number of valid painting schemes. Since the answer could be large, output the result modulo (10^9+7).

inputFormat

The first line contains an integer $k$, the number of paint colors. The second line contains $k$ space-separated integers: $c_1, c_2, \dots, c_k$, where $c_i$ indicates the number of blocks that must be painted with the $i$-th color. It is guaranteed that ( \sum_{i=1}^{k} c_i = n ).

outputFormat

Output a single integer: the number of valid painting schemes modulo (10^9+7).

sample

1
1

1