P7822 「RdOI R3」学习算法

暑假中，MLE 决定学习一下 OI 算法。

暑假一共有 $n$ 天，我们假设 MLE 每天都有足够的时间学 OI。MLE 列出了可供选择的 $m$ 个算法。MLE 每天只能且必须学习一个算法。 而且，MLE 长时间学同一种算法会厌倦，所以每一种算法不能连续学习太多天，第 $i$ 种算法最多可以连续学习 $a_i$ 天。**MLE 没有必要学习全部的算法。** MLE 想知道，自己有多少种不同的学习安排来度过这 $n$ 天。两种学习安排不同仅当这两种安排中有至少一天学习的算法不同。因为方法可能过多，你只需要输出方案数对 $10^9+7$ 取模即可。

第一行为两个整数 $n,m$。 第二行 $m$ 个整数 $a_1,a_2,\cdots,a_m$。

输出一行一个整数，方案数对 $10^9+7$ 取模的结果。

### 样例解释 #### 样例 \#1 第一种算法最多连续学习一天，第二种最多连续学习两天。故共有如下四种学习方式： - $1,2,2$。 - $2,1,2$。 - $2,2,1$。 - $1,2,1$。 #### 样例 \#2 由于唯一的一种算法最多只能连续学习一天，所以没有合法的方案可以度过 $2$ 天。 --- ### 数据范围 **本题采用捆绑测试，若无特殊说明，测试点的内存限制为 256MB。** 对于所有数据，$1\le a_i \le n\le 7 \times 10^3$，$1\le m \le 7\times 10^3$。 | subtask | 分值 | $n,m\le$ | 特殊限制 | | ------- | ---- | -------- | ------------------- | | $1$ | $5$ | $5$ | 无 | | $2$ | $10$ | $100$ | 无 | | $3$ | $15$ | $500$ | 无 | | $4$ | $20$ | $7\times 10^3$ | $a_i=1$ | | $5$ | $20$ | $7\times 10^3$ | 内存限制为 $500$ MB | | $6$ | $30$ | $7\times 10^3$ | 无 |