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.

Examples

Input

3 4
1 2 3


Output

5


Input

1 10
9


Output

0


Input

2 0
0 0


Output

1


Input

4 100000
100000 100000 100000 100000


Output

665683269
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
P=10**9+7

#DP[i][j]=子供iまでで飴j個を分ける(1<=i<=N,0<=j<=K)
DP=[[0]*(K+1) for _ in range(N+1)]
#DP[1][j]を作る
for index1 in range(0,A[1]+1):
    DP[1][index1]=1
#DP[i][0]=1である
for index2 in range(N+1):
    DP[index2][0]=1


for i in range(2,N+1):  #2<=i<=N
    #i固定下で累積和tableを作成
    #C[index]=DP[i-1][0]+...+DP[i-1][index-1](1<=index<=K+1)
    C=[0]*(K+2)
    C[1]=DP[i-1][0]%P
    for c in range(2,K+2):
        C[c]=(C[c-1]+DP[i-1][c-1])%P
    for j in range(1,K+1):  #1<=j<=K
        DP[i][j]=(C[j+1]-C[max(0,j-A[i])])%P




print(DP[N][K]%P)


#for index3 in range(N+1):
    #string=''
    #for index4 in range(K+1):
        #string+=str(DP[index1][index2])+' '
    #print(string)

        






