Description

有 $N$ 个孩子，编号为 $1,2,…,N$。

光头强决定将 $K$ 颗糖果分给他们。这里，对于孩子 $i(1≤i≤N)$ ，必须收到介于 $0$ 和 $a_i$ 之间的糖果（含）。此外，糖果不应有剩余。

找出分配糖果的方案总数，输出模 $10^9+7$ 的结果。如果有任意一个孩子在两个方案中收到糖果的数量不一样，两个方案就认为是不同的。

Input

输入格式如下：

$N\ K\\a_1\ a_2…a_N$

输入中的所有值都是整数。

$1≤N≤100\\0≤K≤10^5\\0≤a_i≤K$

Output

输出孩子们分享糖果的方式，模 $10^9+7$。

Samples

3 4
1 2 3

5

孩子们分享糖果有五种方式，如下：

(0,1,3) (0,2,2) (1,0,3) (1,1,2) (1,2,1)

这里，在每个序列中，第 $i$ 个元素表示第 $i$ 个孩子拿到的糖果数量。

1 10
9

0

也可能不存在按要求分享糖果的方案。

2 0
0 0

1

孩子们有一种分享糖果的方式，如下所示：

(0,0)

4 100000
100000 100000 100000 100000

665683269

务必输出模 $10^9+7$ 的结果。