Problem G
Kaldorian Knights
The number of knights belonging to house $i$ is denoted by $k_i$. Each knight serves at most one house. There can be knights who do not serve any house. The houses are ordered by their influence in the kingdom (with the first one being the most influential). If the $k_1$ knights of the most powerful house take the last $k_1$ places in the tournament, the house will incite a revolt against king and crown. The members of the second most influential house are not that powerful. Even if all its $k_2$ knights end up at the bottom of the ranking, it would be considered a strong provocation but the house would not be able to start a revolt. However, if the last $k_1 + k_2$ places are taken by all the knights of the two most influential houses combined, then the two houses will unite and start fighting the king. More generally, if the knights of the $\ell $ most powerful houses occupy the last $k_1 + k_2 + \dots + k_\ell $ places in the tournament, they will unite and incite a revolt.
Of course, a revolt has to be avoided at all cost. Knowing that the king often chooses the ranking spontaneously and without too much consideration, the chief mathematician of the crown has been tasked with analysing how many rankings will not lead to a revolt.
Input
The input consists of:
-
One line with integers $n$ ($1 \leq n \leq 10^6$) and $h$ ($0 \leq h \leq 5000$), the number of knights and the number of houses.
-
$h$ lines, with the $i$th line containing an integer $k_i$ ($1 \leq k_i \leq n$), denoting the number of knights from house $i$. Note that every house is represented by at least one knight.
It holds that $\sum _{i=1}^h k_i \leq n$.
Output
Output the number of rankings that do not lead to a revolt. As this number can be quite large, it should be output modulo $10^9+7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 0 |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 3 |
18 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 2 2 1 |
16 |
_von_Anhalt.jpg){kind=link}