問題文

$N$ 人の子供たちがいます。 子供たちには $1, 2, \\ldots, N$ と番号が振られています。

子供たちは $K$ 個の飴を分け合うことにしました。 このとき、各 $i$ ($1 \\leq i \\leq N$) について、子供 $i$ が受け取る飴の個数は $0$ 以上 $a_i$ 以下でなければなりません。 また、飴が余ってはいけません。

子供たちが飴を分け合う方法は何通りでしょうか？ $10^9 + 7$ で割った余りを求めてください。 ただし、$2$ 通りの方法が異なるとは、ある子供が存在し、その子供が受け取る飴の個数が異なることを言います。

制約

• 入力はすべて整数である。
• $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

子供たちが飴を分け合う方法は、次の $5$ 通りです。 各数列において、$i$ 番目の要素は子供 $i$ が受け取る飴の個数を表します。

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

---

入力例 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$ で割った余りを出力することを忘れずに。