Description

Xiao P came to the contest site of NOIP2044. He found that the second problem was like this: given a string of length $n$, formed by at most $m$ different characters, where the number of occurrences of the $i$-th character is at most $c_i$, ask what the suffix array of this string is.

Clever Xiao P thought of a new problem and hopes you can help solve it: under the constraints given in the problem, how many different answers can there be. That is, among all strings of length $n$ formed by $m$ characters, where the number of occurrences of the $i$-th character is at most $c_i$, how many different suffix arrays are there in total.

Since the answer is 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 $p_1,p_2,...,p_n$ of $1$ to $n$, satisfying $\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 such that $s_i \neq t_i$. Then the string with the smaller one among $s_i$ and $t_i$ is smaller. If such $i$ does not exist, then the shorter string is smaller.

For the ordering between characters, we define that the $1$-st character is the smallest, the $2$-nd character is the next smallest, and so on.

Input Format

The first line contains two positive integers $n,m$, meaning the length of the string is $n$, and there are $m$ kinds of characters.

The next line contains $m$ non-negative integers $c_1,c_2,...,c_m$, meaning the maximum number of occurrences of 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 one line containing a positive integer, representing the answer.

3 2
2 2

5

10 5
2 3 4 3 2

1003811

Hint

Explanation of Sample 1

Let $a$ be the first kind of character and $b$ be the second kind of character. Then there are $6$ possible strings: $aab,aba,abb,baa,bab,bba$. Their suffix arrays are

So there are $5$ different results.

Constraints

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

Another $10\%$ of the test points: $n, m \leq 10$.

Another $20\%$ of the test points: $n, m \leq 500$. Among them, for $5\%$ of the test points $m = 2$, for $5\%$ of the test points $m = 3$, and for $10\%$ of the test points $c_1 = c_2 = \cdots = c_m = n$.

Another $15\%$ of the test points: $n,m \leq 50$.

Another $20\%$ of the test points: $n, m \leq 200$.

Another $30\%$ of the test points: $n, m \leq 500$.

Translated by ChatGPT 5