Difficulties

You are lining up $n$ problems for a contest. Each problem has one of $k$ difficulty labels. There are $a_i$ problems with label $i$, and $a_1 + a_2 + \cdots + a_k = n$.

Problems with the same label are indistinguishable. Problems with different labels are distinct. Count the number of distinct ordered problemsets (sequences of length $n$). Since the answer can be large, output it modulo $10^9 + 7$.

Input

The first line contains two integers $n$ and $k$.

The second line contains $k$ integers $a_1, a_2, \ldots, a_k$.

It is guaranteed that $a_1 + a_2 + \cdots + a_k = n$.

Output

Print one integer: the number of distinct ordered problemsets, modulo $10^9 + 7$.

Constraints

• $1 \le k \le n \le 10^6$
• $0 \le a_i \le n$
• $a_1 + a_2 + \cdots + a_k = n$

Example 1

3 2
2 1

3

Explanation

Write $A$ for label $1$ and $B$ for label $2$. The distinct sequences are $AAB$, $ABA$, and $BAA$.

Example 2

4 4
1 1 1 1

24

Explanation

Every problem has a distinct label, so every permutation of the $4$ problems is distinct: $4! = 24$.

Example 3

6 3
3 2 1

60

Explanation

If the labels were all distinct there would be $6!$ sequences. The three copies of the first label are indistinguishable, as are the two copies of the second, so divide by $\dfrac{6!}{3! \, 2! \, 1!} = 60$.