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