AT_dp_m Candies

[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/A

N/A

### 制約 - 入力はすべて整数である。 - $ 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 $ で割った余りを出力することを忘れずに。