Candies

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

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_m $ 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 $ で割った余りを出力せよ。

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