问题描述

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

这些孩子决定分享 $K$ 个糖果。对于每个 $i$ ($1 \leq i \leq N$)，孩子 $i$ 可以获得的糖果数量必须在 $0$ 到 $a_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\ …\ a_N$

输出

输出孩子们分享糖果的方法数，对 $10^9 + 7$ 取模后的余数。

输入示例 1

3 4
1 2 3

输出示例 1

5

孩子们分享糖果的方法有以下 5 种：

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

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

输入示例 2

1 10
9

输出示例 2

0

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

输入示例 3

2 0
0 0

输出示例 3

1

孩子们分享糖果的方法有以下 1 种：

• (0, 0)

输入示例 4

4 100000
100000 100000 100000 100000

输出示例 4

665683269

请确保输出结果对 $10^9 + 7$ 取模后的余数。