题目描述

现在有x个相同的小球，分给y个人，每个人至少分a[i]个，请问有多少种可能的分发方法，答案对$10^9+7$取模。

输入格式

第一行2个整数，分别表示x个小球，和y个人.(x<=1000000,y<=1000) 第二行y个整数，第i个整数表示，第i个人至少需要分到的小球数量a[i],((a[i]<=1000))

输出格式

一个整数，表示答案对10^9+7 取模的结果

样例 #1

样例输入 #1

10 3
0 1 4

样例输出 #1

21

样例 #2

样例输入 #2

20 4
1 2 3 4

样例输出 #2

286