Problem Statement

There are $N$ children, numbered $1,2,\\ldots,N$. In the next $K$ days, we will give them some cookies. In the $i$-th day, we will choose $a_i$ children among the $N$ with equal probability, and give one cookie to each child chosen. (We make these $K$ choices independently.)

Let us define the happiness of the children as $c_1 \\times c_2 \\times \\ldots \\times c_N$, where $c_i$ is the number of cookies received by Child $i$ in the $K$ days. Find the expected happiness multiplied by $\\binom{N}{a_1} \\times \\binom{N}{a_2} \\times \\ldots \\times \\binom{N}{a_K}$ (we can show that this value is an integer), modulo $(10^{9}+7)$.

Notes

$\\binom{n}{k}$ denotes the number of possible choices of $k$ objects out of given distinct $n$ objects, disregarding order.

Constraints

• $1 \\leq N \\leq 1000$
• $1 \\leq K \\leq 20$
• $1 \\leq a_i \\leq N$

Input

Input is given from Standard Input in the following format:

$N$ $K$ $a_1$ $a_2$ $\\ldots$ $a_K$

Output

Print the answer.

Sample Input 1

3 2
3 2

Sample Output 1

12

• On the first day, all the children $1$, $2$, and $3$ receive one cookie.
• On the second day, two out of the three children $1$, $2$, and $3$ receive one cookie.
• Their happiness is $4$ in any case, so the expected happiness is $4$. Print this value multiplied by $\\binom{3}{3} \\times \\binom{3}{2}$, which is $12$.

Sample Input 2

856 16
399 263 665 432 206 61 784 548 422 313 848 478 827 26 398 63

Sample Output 2

337587117

• Find the expected value multiplied by $\\binom{N}{a_1} \\times \\binom{N}{a_2} \\times \\ldots \\times \\binom{N}{a_K}$, modulo $(10^9+7)$.