Problem Description

Little P has arrived at the NOIP2044 competition, where he found the second problem to be as follows: Given a string of length $n$, composed of at most $m$ different characters, where the number of occurrences of the $i$-th character does not exceed $c_i$, determine the suffix array of this string.

Clever Little P has come up with a new problem for you to solve: Under the given constraints, how many different possible answers are there? That is, how many different suffix arrays can be formed from strings of length $n$ composed of $m$ characters, where the number of occurrences of the $i$-th character does not exceed $c_i$.

Since the answer can be very large, you only need to output the answer modulo $10^9+7$.

For a string $s = s_1s_2...s_n$, let $\mathrm{suf}(i)$ denote the substring from position $i$ to the end. The suffix array is a permutation of $1$ to $n$, denoted as $p_1, p_2, ..., p_n$, such that $\mathrm{suf}(p_1) < \mathrm{suf}(p_2) < \dots < \mathrm{suf}(p_n)$. For two strings $s$ and $t$, let $i$ be the first position where $s_i \neq t_i$. Then the string with the smaller character at position $i$ is considered smaller. If such an $i$ does not exist, the shorter string is considered smaller.

The order of characters is defined such that the first character is the smallest, the second character is the next smallest, and so on.

Input Format

The first line of input contains two positive integers $n$ and $m$, representing the length of the string and the number of different characters, respectively.

The next line contains $m$ non-negative integers $c_1, c_2, ..., c_m$, representing the maximum number of occurrences for each character. It is guaranteed that $0 \leq c_1, c_2, ..., c_m \leq n$ and $c_1 + c_2 + ... + c_m \geq n$.

Output Format

Output a single line containing a positive number, representing the answer.

Sample Input and Output

Sample Input #1

3 2
2 2

Sample Output #1

5

Sample Input #2

10 5
2 3 4 3 2

Sample Output #2

1003811

Notes

Sample One Explanation

Let's denote the first character as $a$ and the second character as $b$. There are six possible strings: $aab, aba, abb, baa, bab, bba$. Their suffix arrays are:

$$(1,2,3), (3,1,2), (1,3,2), (3,2,1), (2,3,1), (3,2,1)$$

Thus, there are 5 different results.

Data Range

For the first $5\%$ of test cases, $n, m \leq 6$.

For another $10\%$ of test cases, $n, m \leq 10$.

For another $20\%$ of test cases, $n, m \leq 500$, including $5\%$ with $m = 2$, $5\%$ with $m = 3$, and $10\%$ with $c_1 = c_2 = \cdots = c_m = n$.

For another $15\%$ of test cases, $n, m \leq 50$.

For another $20\%$ of test cases, $n, m \leq 200$.

For another $30\%$ of test cases, $n, m \leq 500$.

见题面 Input 部分

见题面 Output 部分