学校刚刚到了一批新书，教导主任现在想找 m 位学生把这些书搬到仓库里。
已知学校一共有 n 个班,编号分别为1,2,3,..,n。编号为 i 的班级里有 a_i 位学生。
现在,教导主任打算从这 n 个班里每个班随机挑选若干名学生去搬书,请问一共有多少种可能的挑选方案。因为答案可能会很大，所以答案请对10^9+7取模。
输入
第一行包括两个整数 n 和 m
第二行包括 n 个整数,第i个整数代表 a_i
1 \leq n \leq 100
1 \leq m \leq 1000
1 \leq a_i \leq 1000
数据保证每个班级的人数之和不小于 m
输出
输出一个整数,表示答案
样例
| 标准输入 复制文本 |
2 3 4 4 |
| 标准输出 复制文本 |
4 |
| 标准输入 复制文本 |
3 4 3 2 3 |
| 标准输出 复制文本 |
10 |
| 标准输入 复制文本 |
5 1000 997 998 993 992 991 |
| 标准输出 复制文本 |
84792402 |
提示
在第一个样例中,共有[0,3]、[1,2]、[2,1]、[3,0]四种可能
在第二个样例中,共有[0,1,3]、[0,2,2]、[1,0,3]、[1,1,2]、[1,2,1]、[2,0,2]、[2,1,1]、[2,2,0]、[3,0,1]、[3,1,0]十种可能。
( [ ]内的数为在每个班里分别挑选的人数 )