题目描述

小婷准备把 $K$ 颗完全相同的糖果分给 $N$ 名学生，学生编号为 $1,2,\ldots,N$。

每名学生能够接受的糖果数量不同。对于学生 $i$，他得到的糖果数必须在 $0$ 到 $a_i$ 之间，包括两个端点。所有 $K$ 颗糖果都必须分完，不能有任何剩余。

如果在两种分配方案中，至少存在一名学生得到的糖果数量不同，就认为这两种方案不同。糖果本身完全相同，因此只考虑每名学生最终得到的数量。

请计算一共有多少种合法的分配方案。由于答案可能非常大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行输入两个整数 $N,K$。

第二行输入 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出格式

输出一个整数，表示合法分配方案数对 $10^9+7$ 取模后的结果。

3 4
1 2 3

5

样例说明 #1

五种方案分别为 $(0,1,3)$、$(0,2,2)$、$(1,0,3)$、$(1,1,2)$、$(1,2,1)$。

1 10
9

0

样例说明 #2

唯一的学生最多只能得到 $9$ 颗糖果，无法分完 $10$ 颗，因此不存在合法方案。

2 0
0 0

1

样例说明 #3

没有糖果需要分配，两名学生都得到 $0$ 颗是唯一方案。

数据范围与约定

$1\le N\le100$，$0\le K\le10^5$，$0\le a_i\le K$。输入中的所有数均为整数。