Kaldoria 的国王习惯通过举办一场盛大的比武大赛来庆祝他的生日，王国中的每个贵族家族都会派遣他们最优秀的骑士来赢取名声与荣耀。在比赛结束时，国王不仅会选出获胜者，还会将所有 $n$ 名骑士从最差到最好进行排名。

我们将属于家族 $i$ 的骑士数量记为 $k_i$。每名骑士最多只效忠于一个家族。也存在不效忠于任何家族的骑士。家族按其在王国中的影响力进行排序（第一个家族影响力最大）。如果影响力最大的家族的 $k_1$ 名骑士占据了比赛排名的最后 $k_1$ 位，该家族就会煽动针对国王和王权的叛乱。影响力第二大的家族成员实力没那么强。即使其全部 $k_2$ 名骑士都排在最后，这会被视为一种强烈的挑衅，但该家族尚不足以发动叛乱。然而，如果最后 $k_1 + k_2$ 个名次被影响力最大的两个家族的所有骑士共同占据，那么这两个家族就会联合起来对抗国王。更一般地，如果影响力最大的 $\ell$ 个家族的骑士占据了比赛排名的最后 $k_1 + k_2 + \dots + k_\ell$ 位，他们就会联合起来煽动叛乱。

当然，必须不惜一切代价避免叛乱。由于国王经常随意且不加过多考虑地进行排名，王室的首席数学家被指派分析有多少种排名方式不会导致叛乱。

输入格式

输入包含： 一行包含整数 $n$ ($1 \le n \le 10^6$) 和 $h$ ($0 \le h \le 5000$)，分别表示骑士的总数和家族的数量。 $h$ 行，第 $i$ 行包含一个整数 $k_i$ ($1 \le k_i \le n$)，表示来自家族 $i$ 的骑士数量。注意每个家族至少有一名骑士。 满足 $\sum_{i=1}^h k_i \le n$。

输出格式

输出不会导致叛乱的排名数量。由于该数字可能非常大，请将其对 $10^9 + 7$ 取模后输出。

中世纪比武大赛的画作，出自《马内塞古抄本》(Codex Manesse)。

样例

样例输入 1

3 0

样例输出 1

6

样例输入 2

4 1
3

样例输出 2

18

样例输入 3

4 2
2
1

样例输出 3

16