配点 : $100$ 点

問題文

$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$ で割った余りを出力せよ。

3 4
1 2 3

5

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

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

1 10
9

0

子供たちが飴を分け合う方法が存在しない場合もあります。

2 0
0 0

1

子供たちが飴を分け合う方法は、次の $1$ 通りです。

• $(0, 0)$

4 100000
100000 100000 100000 100000

665683269

答えを $10^9 + 7$ で割った余りを出力することを忘れずに。