Problem Description

There are $ N $ children, numbered $1, 2, \ldots, N$. For the next $ K $ days, cookies will be distributed to the children. On the $ i $-th day, $ a_i $ children are chosen uniformly at random from the $ N $ children, and each of the chosen children receives one cookie. (The selection of children for each day is done independently.)

Let $ c_i $ be the number of cookies received by child $ i $ over the $ K $ days. The happiness of the children is defined as $c_1 \times c_2 \times \ldots \times c_N$. Calculate the remainder when the expected happiness multiplied by $\binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K}$ (which can be shown to be an integer) is divided by $ 10^9+7 $.

Input Format

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

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

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 2
3 2

Sample Output #1

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

Notes/Hints

Notes

$\binom{n}{k}$ represents the number of ways to choose $ k $ items from $ n $ distinct items.

Constraints

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

Sample Explanation 1

• On the first day, all children $ 1, 2, 3 $ receive a cookie.
• On the second day, one of the children $ 1, 2, 3 $ does not receive a cookie.
• In all cases, the happiness is $ 4 $, so the expected happiness is $ 4 $. Output the value of $4 \times \binom{3}{3} \times \binom{3}{2}$, which is $ 12 $.

Sample Explanation 2

• Calculate the remainder when the expected happiness multiplied by $\binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K}$ is divided by $ 10^9+7 $.

见题面 Input 部分

见题面 Output 部分