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
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception addd) {
					addd.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception addd) {
				addd.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	
	public static FastReader sc = new FastReader();
 
	static int mod = (int) (1e9+7),MAX=(int) (2e5);
    static List<Integer>[] edges;
    static long[][] dp;
    static int k,n;
    static int[] a;
	public static void main(String[] args) {
	    n = sc.nextInt();
	    k = sc.nextInt();
	    dp = new long[n+1][k+1];
	    a = new int[n+1];
	    for(int i=1;i<=n;++i) a[i] = sc.nextInt();
	    for(int j=0;j<=k;++j) dp[1][j] = (j > a[1])?0:1;
	    
	    for(int i=2;i<=n;++i) {
	    	for(int j=0;j<=k;++j) {
	    	    if(j == 0) dp[i][j] = dp[i-1][j];
	    	    else {
	    	    	dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
	    	    	if(j-1-a[i] >= 0) dp[i][j] = (dp[i][j] - dp[i-1][j-1-a[i]] + mod)%mod;
	    	    }
	    	}
	    }
	    out.print(dp[n][k]);
		out.close();
   }
	
	
}

