题目描述

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

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

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

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

子供たちが飴を分け合う方法は何通りか？ $10^9\ +\ 7$ で割った余りを出力せよ。

题目大意

$K$ 颗糖分给 $n$ 个人，第 $i$ 个人至少分得 $0$ 颗，至多分得 $a_i$ 颗，必须分完，求方案数，答案对 $10^9+7$ 取模。

3 4
1 2 3

5

1 10
9

0

2 0
0 0

1

4 100000
100000 100000 100000 100000

665683269

提示

制約

• 入力はすべて整数である。
• $1\ \leq\ N\ \leq\ 100$
• $0\ \leq\ K\ \leq\ 10^5$
• $0\ \leq\ a_i\ \leq\ K$

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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