Kaldorian Knights

The king of Kaldoria traditionally celebrates his birthday by inviting the knights of his realm to a big jousting tournament, and every noble house participates by sending their best knights to win fame and glory. At the end of the tournament, the king does not only choose a winner but ranks all $n$ knights from worst to best.

The number of knights belonging to house $i$ is denoted by $k_i$. Each knight serves at most one house. Some knights may 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 the king and crown. The members of the second most influential house are not that powerful. Even if all $k_2$ of its knights end up at the bottom of the ranking, it would be 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, the two houses will unite and fight 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.

A revolt must be avoided at all cost. The king often chooses the ranking on the spot without much thought, so the chief mathematician of the crown has been asked to count how many rankings will not lead to a revolt.

The first line contains integers $n$ ($1 \leq n \leq 10^6$) and $h$ ($0 \leq h \leq 5000$), the number of knights and the number of houses. Then $h$ lines follow, where the $i$-th line contains an integer $k_i$ ($1 \leq k_i \leq n$), the number of knights from house $i$. Every house has at least one knight. It holds that $\sum_{i=1}^h k_i \leq n$.

Output the number of rankings that do not lead to a revolt, modulo $10^9+7$, since this number can be quite large.