Description

卡尔多利亚的国王通常会在生日时举办一场盛大的骑士比武大会，邀请王国中的骑士们参加，每个贵族家族都会派出最优秀的骑士来争夺荣誉和名声。在比赛结束时，国王不仅会选出冠军，还会将所有 $n$ 名骑士从最差到最好进行排名。

:::align{center} 中世纪比武大会的画作，出自 Codex Manesse。 :::

第 $i$ 个家族拥有的骑士数量为 $k_i$。每名骑士最多只属于一个家族，也可能有骑士不属于任何家族。家族按照在王国中的影响力从高到低排序（第一个家族最有影响力）。

如果最有影响力的家族的 $k_1$ 名骑士在比赛中占据了最后 $k_1$ 个名次，这个家族就会煽动叛乱反对国王和王国。第二有影响力的家族虽然没有那么强大，即使他们的 $k_2$ 名骑士全部排在最后，也只是被视为强烈的挑衅，但还不足以发动叛乱。然而，如果最后 $k_1 + k_2$ 个名次被最有影响力的两个家族的所有骑士占据，这两个家族就会联合起来反抗国王。

更一般地说，如果排名最后的 $k_1 + k_2 + \dots + k_\ell$ 个名次被前 $\ell$ 个最有影响力家族的所有骑士占据，这些家族就会联合起来煽动叛乱。

当然，必须不惜一切代价避免叛乱。由于国王经常随意决定排名，你作为王国的首席数学家需要分析有多少种排名不会导致叛乱。

形式化题意

给定长为 $h$ 的数列 $k_i$，求满足下列条件的长为 $n$ 的排列 $p_j$ 的数量：

• 对于每一个 $1 \leq i \leq h$，存在 $n-\sum_{l=1}^i{k_l}+1 \leq j \leq n$，使得 $p_j>\sum_{l=1}^i{k_l}$。

Input Format

输入包括：

• 第一行包含两个整数 $n$（$1 \leq n \leq 10^6$）和 $h$（$0 \leq h \leq 5000$），分别表示骑士总数和家族数。
• 接下来 $h$ 行，每行一个整数 $k_i$（$1 \leq k_i \leq n$），表示第 $i$ 个家族的骑士数量。每个家族至少有一名骑士。

保证 $\sum_{i=1}^h k_i \leq n$。

Output Format

输出不会导致叛乱的排名方案数。由于答案可能很大，请输出对 $10^9+7$ 取模的结果。

3 0

6

4 1
3

18

4 2
2
1

16

Hint

由 ChatGPT 4.1 翻译