测试数据来自 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