测试数据来自 system/3011

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给定方程：\(x_1+x_2+...+x_n=m\)，其中：\(x_1,x_2,…,x_n\) 为整数，\(m\) 为正整数。

　　再给定关于 \(x_i\) 的约束条件，即要求：\(x_i≥a_i\)。

　　请你编程计算在满足约束条件的情况下，方程的解的个数。

【输入格式】

　　第一行包含两个整数：\(m,n\)。它们的意义如题目描述。
　　接下来有 \(n\) 行，每行包含一个整数：\(a_i\)，表示要求 \(x_i≥a_i\)。

【输出格式】

　　若存在满足条件的解，则输出方程不同的解的个数，这个数可能很大，你只需输出 \(mod\ 10^8+7\) 的结果。若没有解，则输出 None。

【输入输出样例1】

　Input

8 3
2
0
3

　Output

10

【样例解释】

　　有10组满足约束条件的解，分别为：
　　\(x_1=2，x_2=0，x_3=6\)；即：2 + 0 + 6 = 8
　　\(x_1=2，x_2=1，x_3=5\)；即：2 + 1 + 5 = 8
　　\(x_1=2，x_2=2，x_3=4\)；即：2 + 2 + 4 = 8
　　\(x_1=2，x_2=3，x_3=3\)；即：2 + 3 + 3 = 8
　　\(x_1=3，x_2=0，x_3=5\)；即：3 + 0 + 5 = 8
　　\(x_1=3，x_2=1，x_3=4\)；即：3 + 1 + 4 = 8
　　\(x_1=3，x_2=2，x_3=3\)；即：3 + 2 + 3 = 8
　　\(x_1=4，x_2=0，x_3=4\)；即：4 + 0 + 4 = 8
　　\(x_1=4，x_2=1，x_3=3\)；即：4 + 1 + 3 = 8
　　\(x_1=5，x_2=0，x_3=3\)；即：5 + 0 + 3 = 8

【输入输出样例2】

　Input

10 4
3
-1
4
0

　Output

35

【数据说明】

　　对于 \(40\%\) 的数据 \(1≤n≤10\)，\(0≤m≤100\)，\(|a_i|≤5\)
　　对于 \(100\%\) 的数据 \(1≤m+n≤2000\)，\(|a_i|≤30\)且 所有 \(|ai|\) 之和不大于 1000。

【来源】

　　Mr.he