6722: 学习算法

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

### 样例输入 #1

```
3 2
1 2
```

### 样例输出 #1

```
4
```

## 样例 #2

### 样例输入 #2

```
2 1
1
```

### 样例输出 #2

```
0
```

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

### 样例解释

#### 样例 \#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$   | 无                 |