P5417 [CTSC2016] Suffix Array

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.

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 one line containing a positive integer, representing the answer.

### 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 $$(1,2,3),(3,1,2),(1,3,2),(3,2,1),(2,3,1),(3,2,1)$$ 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