题目背景

暑假中，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$ 取模的结果。

3 2
1 2

4

2 1
1

0

8 5
4 2 3 4 2

356314

提示

样例解释

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