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

Input

3 2
2 1

Output

3

Explanation

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

Example 2

Input

4 4
1 1 1 1

Output

24

Explanation

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

Example 3

Input

6 3
3 2 1

Output

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~.