问题陈述

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

他们决定分享 $K$ 颗糖果。对于每个 $i$ ( $1 \leq i \leq N$ )，第 $i$ 个孩子必须分得 $0$ 到 $a_i$ 颗糖果(包括首尾两颗)。此外，糖果不能剩余。

求他们分享糖果的方法数，模数为 $10^9 + 7$ 。在这里，如果有一个孩子分到的糖果数量不同，那么这两种分法就是不同的。

限制因素

• 输入值均为整数
• $1 \leq N \leq 100$
• $0 \leq K \leq 10^5$
• $0 \leq a_i \leq K$

输入

输入内容由标准输入法提供，格式如下：

• $N$ $K$
• $a_1$ $a_2$ $\ldots$ $a_N$

输出

打印孩子们分享糖果的方式数，对 $10^9 + 7$ 取模。

3 4
1 2 3

5

孩子们有以下五种分享糖果的方式：

• $(0, 1, 3)$
• $(0, 2, 2)$
• $(1, 0, 3)$
• $(1, 1, 2)$
• $(1, 2, 1)$

在这里，每个序列中的 $i$ -th 元素代表孩子 $i$ 收到的糖果数量。

1 10
9

0

孩子们可能没有办法分享糖果。

2 0
0 0

1

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

• $(0, 0)$

4 100000
100000 100000 100000 100000

665683269

请务必打印出答案的模数 $10^9 + 7$ 。

来源

https://atcoder.jp/contests/dp/tasks/dp_m