There are ~N~ children, numbered ~1, 2, \dots, N~.

They have decided to share ~K~ candies among themselves. Here, for each ~i~ ~(1 \le i \le 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 \le N \le 100~
• ~0 \le K \le 10^5~
• ~0 \le a_i \le K~

Input Specification

The first line will contain 2 space separated integers ~N~ and ~K~.

The next line will contain ~N~ integers, ~a_1, a_2, \dots, a_N~.

Output Specification

Print the number of ways for the children to share candies, modulo ~10^9+7~.

Note: Be sure to print the answer modulo ~10^9+7~.

Sample Input 1

3 4
1 2 3

Sample Output 1

5

Explanation for Sample 1

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

Explanation for Sample 2

There may be no ways for the children to share candies.

Sample Input 3

2 0
0 0

Sample Output 3

1

Explanation for Sample 3

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