题目描述

有 $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$。

---

示例输入 1

3 4
1 2 3

示例输出 1

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

以下是孩子分享糖果的一种方式：

• $(0, 0)$

---

示例输入 4

4 100000
100000 100000 100000 100000

示例输出 4

665683269

请务必将答案取模 $10^9 + 7$。