/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 で割った余りを出力せよ。
入力例 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 で割った余りを出力することを忘れずに。
Score : 100 points
Problem Statement
There are N children, numbered 1, 2, \ldots, N.
They have decided to share K candies among themselves. Here, for each i (1 \leq i \leq N), Child i must receive between 0 and a_i candies (inclusive). Also, no candies should be left over.
Find the number of ways for them to share candies, modulo 10^9 + 7. Here, two ways are said to be different when there exists a child who receives a different number of candies.
Constraints
- All values in input are integers.
- 1 \leq N \leq 100
- 0 \leq K \leq 10^5
- 0 \leq a_i \leq K
Input
Input is given from Standard Input in the following format:
N K a_1 a_2 \ldots a_N
Output
Print the number of ways for the children to share candies, modulo 10^9 + 7.
Sample Input 1
3 4 1 2 3
Sample Output 1
5
There are five ways for the children to share candies, as follows:
- (0, 1, 3)
- (0, 2, 2)
- (1, 0, 3)
- (1, 1, 2)
- (1, 2, 1)
Here, in each sequence, the i-th element represents the number of candies that Child i receives.
Sample Input 2
1 10 9
Sample Output 2
0
There may be no ways for the children to share candies.
Sample Input 3
2 0 0 0
Sample Output 3
1
There is one way for the children to share candies, as follows:
- (0, 0)
Sample Input 4
4 100000 100000 100000 100000 100000
Sample Output 4
665683269
Be sure to print the answer modulo 10^9 + 7.