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.util.*;

public class Main {
	static PrintWriter out;
	static StringBuilder sb;
	static long mod = 1000000007;
	static long[] fac;
	static int []si;
	static int []a;
	static int n,k;
	static ArrayList<Integer> primes;
	static HashMap<Integer,Integer> factors;
	static HashSet<Integer> [] divisors;
	static long memo[][];
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
	    n=sc.nextInt();
	    k=sc.nextInt();
	    a=new int [n];
	    for(int i=0;i<n;i++)
	    	a[i]=sc.nextInt();
	    memo=new long[n+1][k+1];
	  //  for(long []h:memo)
	    //	Arrays.fill(h,-1);
	    dp(0);
	//    for(long []h:memo)
	  //  	System.out.println(Arrays.toString(h));
	    out.println(memo[0][k]);
		out.flush();
	}
	static void dp(int i) {
		if(i==n-1) {
			for(int j=0;j<=Math.min(k, a[i]);j++)
			          	memo[i][j]=1l;
			return;
		}
		dp(i+1);
		long []ans=new long[k+1];
		for(int j=0;j<=k;j++) {
			if(j==0)
				ans[j]=memo[i+1][0];
			else
				ans[j]=(memo[i+1][j]+ans[j-1])%mod;
		}
		for(int j=0;j<=k;j++) {
			if(j>a[i]) {
				memo[i][j]=(ans[j]-ans[j-a[i]-1]+mod)%mod;
			}
			else {
				memo[i][j]=ans[j];
			}
		}
	}
   static void factor(int n) {
	   if(si[n]==n) {
		   factors.put(n, factors.getOrDefault(n, 0)+1);
		   return;
	   }
	   factors.put(si[n], factors.getOrDefault(si[n], 0)+1);
	 
	   factor(n/si[(int)n]);
   }
   static void findFactors(int idx,int[] primeDivisors, int[] multiplicity, int currentDivisor, int currentResult) {
	    if (currentDivisor == primeDivisors.length) {
	        divisors[idx].add(currentResult);
	        return;
	    }
	    // how many times will we take current divisor?
	    // we have to try all options
	    for (int i = 0; i <= multiplicity[currentDivisor]; ++i) {
	        findFactors(idx,primeDivisors, multiplicity, currentDivisor + 1, currentResult);
	        currentResult *= primeDivisors[currentDivisor];
	    }
	}
 	static long inver(long x) {
		int a = (int) x;
		long e = (mod - 2);
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1) {
				// System.out.println(res*a);
				res = (int) ((1l * res * a) % mod);
			}
			a = (int) ((1l * a * a) % mod);
			e >>= 1;
		}
		// out.println(res+" "+x);
		return res % mod;
	}

	static public class segmentTree {
		int[] array, lazy;
		sol[] tree;
		int n;

		segmentTree(int[] aa) {
			array = aa;
			n = array.length - 1;
			tree = new sol[n * 4];
			// lazy = new int[n * 4];
			// Arrays.fill(lazy, -1);
			build(1, 1, n);
		}

		public String toString() {
			return Arrays.toString(tree);
		}

		void build(int node, int l, int r) {
			if (l == r)
				tree[node] = new sol(true, array[r], array[r], 'e');
			else {
				int mid = (l + r) >> 1;
				build(node << 1, l, mid);
				build((node << 1) | 1, mid + 1, r);
				if (!tree[node << 1].st || !tree[(node << 1) | 1].st) {
					tree[node] = new sol(false, tree[node << 1].l, tree[node << 1 | 1].r, 'n');
				} else if (tree[node << 1].s == 'l' && tree[(node << 1) | 1].s == 'l') {
					tree[node] = new sol(false, tree[node << 1].l, tree[node << 1 | 1].r, 'n');
				} else if (tree[node << 1].s == 'l') {
					if (tree[(node << 1) | 1].s == 'e' && tree[(node << 1) | 1].l <= tree[(node << 1)].r)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 'l');
					else if (tree[(node << 1) | 1].s == 's' && tree[(node << 1) | 1].l >= tree[(node << 1) | 1].r
							&& tree[(node << 1) | 1].l <= tree[(node << 1)].r)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 'l');
					else
						tree[node] = new sol(false, tree[node << 1].l, tree[node << 1 | 1].r, 'n');
				} else if (tree[(node << 1) | 1].s == 'l') {
					if (tree[(node << 1)].s == 'e' && tree[(node << 1)].r <= tree[(node << 1) | 1].l)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 'l');
					else if (tree[(node << 1)].s == 's' && tree[(node << 1)].r >= tree[(node << 1)].l
							&& tree[(node << 1)].r <= tree[(node << 1) | 1].l)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 'l');
					else
						tree[node] = new sol(false, tree[node << 1].l, tree[node << 1 | 1].r, 'n');
				} else if (tree[node << 1].s == 'e' && tree[(node << 1) | 1].s == 'e') {
					tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 's');
				} else if (tree[node << 1].s == 's' && tree[(node << 1) | 1].s == 's') {
					if (tree[node << 1].r >= tree[node << 1].l && tree[node << 1 | 1].r <= tree[node << 1 | 1].l)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 'l');
					else if (tree[node << 1].r >= tree[node << 1].l && tree[node << 1 | 1].l >= tree[node << 1].r
							&& tree[node << 1 | 1].r >= tree[node << 1 | 1].l)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 's');
					else if (tree[node << 1].l >= tree[node << 1].r && tree[node << 1 | 1].l <= tree[node << 1].r
							&& tree[node << 1 | 1].l >= tree[node << 1 | 1].r)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 's');
					else
						tree[node] = new sol(false, tree[node << 1].l, tree[node << 1 | 1].r, 'n');
				} else if (tree[node << 1].s == 's') {
					if (tree[node << 1].r >= tree[node << 1].l && tree[node << 1 | 1].l >= tree[node << 1].r)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 's');
					else if (tree[node << 1].r >= tree[node << 1].l)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 'l');
					else if (tree[node << 1].l >= tree[node << 1].r && tree[node << 1 | 1].l <= tree[node << 1].r)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 'l');
					else
						tree[node] = new sol(false, tree[node << 1].l, tree[node << 1 | 1].r, 'n');
				} else if (tree[(node << 1) | 1].s == 's') {
					if (tree[node << 1 | 1].r >= tree[node << 1 | 1].l && tree[node << 1].r <= tree[node << 1 | 1].l)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 's');
					else if (tree[node << 1 | 1].r >= tree[node << 1 | 1].l)
						tree[node] = new sol(false, tree[node << 1].l, tree[node << 1 | 1].r, 'n');
					else if (tree[node << 1 | 1].l >= tree[node << 1 | 1].r
							&& tree[node << 1].r >= tree[node << 1 | 1].l)
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 's');
					else
						tree[node] = new sol(true, tree[node << 1].l, tree[node << 1 | 1].r, 'l');
				}
				// else
				// tree[node]=new sol(false,tree[node<<1].l,tree[node<<1|1].r,'n');
			}
		}

		/*
		 * void updateRange(int i, int j, int v) { updateR(1, 1, n, i, j, v); }
		 * 
		 * void updateR(int node, int l, int r, int i, int j, int v) { if (i > r || j <
		 * l) return; if (i <= l && j >= r) { tree[node] = (r - l + 1) * v; lazy[node] =
		 * v; } else { int mid = l + r >> 1; propagate(node, l, mid, r); updateR(node <<
		 * 1, l, mid, i, j, v); updateR(node << 1 | 1, mid + 1, r, i, j, v); tree[node]
		 * = tree[node << 1] + tree[node << 1 | 1]; } }
		 * 
		 * void propagate(int node, int b, int mid, int e) { if (lazy[node] != -1) {
		 * lazy[node << 1] = lazy[node]; lazy[node << 1 | 1] = lazy[node]; tree[node <<
		 * 1] = (mid - b + 1) * lazy[node]; tree[node << 1 | 1] = (e - mid) *
		 * lazy[node]; } lazy[node] = -1; }
		 */

		sol query(int i, int j) {
			return query(1, 1, n, i, j);
		}

		sol query(int node, int b, int e, int i, int j) // O(log n)
		{
			if (i > e || j < b)
				return null;
			if (b >= i && e <= j)
				return tree[node];
			int mid = b + e >> 1;
//			propagate(node, b, mid, e);
			sol q1 = query(node << 1, b, mid, i, j);
			sol q2 = query(node << 1 | 1, mid + 1, e, i, j);
			if (q1 == null)
				return q2;
			if (q2 == null)
				return q1;
			sol q3 = null;
			if (!q1.st || !q2.st) {
				q3 = new sol(false, q1.l, q2.r, 'n');
			} else if (q1.s == 'l' && q2.s == 'l') {
				q3 = new sol(false, q1.l, q2.r, 'n');
			} else if (q1.s == 'l') {
				if (q2.s == 'e' && q2.l <= q1.r)
					q3 = new sol(true, q1.l, q2.r, 'l');
				else if (q2.s == 's' && q2.l >= q2.r && q2.l <= q1.r)
					q3 = new sol(true, q1.l, q2.r, 'l');
				else
					q3 = new sol(false, q1.l, q2.r, 'n');
			} else if (q2.s == 'l') {
				if (q1.s == 'e' && q1.r <= q2.l)
					q3 = new sol(true, q1.l, q2.r, 'l');
				else if (q1.s == 's' && q1.r >= q1.l && q1.r <= q2.l)
					q3 = new sol(true, q1.l, q2.r, 'l');
				else
					q3 = new sol(false, q1.l, q2.r, 'n');
			} else if (q1.s == 'e' && q2.s == 'e') {
				q3 = new sol(true, q1.l, q2.r, 's');
			} else if (q1.s == 's' && q2.s == 's') {
				if (q1.r >= q1.l && q2.r <= q2.l)
					q3 = new sol(true, q1.l, q2.r, 'l');
				else if (q1.r >= q1.l && q2.l >= q1.r && q2.r >= q2.l)
					q3 = new sol(true, q1.l, q2.r, 's');
				else if (q1.l >= q1.r && q2.l <= q1.r && q2.l >= q2.r)
					q3 = new sol(true, q1.l, q2.r, 's');
				else
					q3 = new sol(false, q1.l, q2.r, 'n');
			} else if (q1.s == 's') {
				if (q1.r >= q1.l && q2.l >= q1.r)
					q3 = new sol(true, q1.l, q2.r, 's');
				else if (q1.r >= q1.l)
					q3 = new sol(true, q1.l, q2.r, 'l');
				else if (q1.l >= q1.r && q2.l <= q1.r)
					q3 = new sol(true, q1.l, q2.r, 'l');
				else
					q3 = new sol(false, q1.l, q2.r, 'n');
			} else if (q2.s == 's') {
				if (q2.r >= q2.l && q1.r <= q2.l)
					q3 = new sol(true, q1.l, q2.r, 's');
				else if (q2.r >= q2.l)
					q3 = new sol(false, q1.l, q2.r, 'n');
				else if (q2.l >= q2.r && q1.r >= q2.l)
					q3 = new sol(true, q1.l, q2.r, 's');
				else
					q3 = new sol(true, q1.l, q2.r, 'l');
			}
			return q3;

		}

	}

	static long fac(int n) {
		if (n == 0)
			return fac[n] = 1;
		if (n == 1)
			return fac[n] = 1;
		long ans = 1;
		for (int i = 1; i <= n; i++)
			fac[i] = ans = (i % mod * ans % mod) % mod;
		return ans % mod;
	}

	static long gcd(long a, long b) {

		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	static class sol {
		boolean st;
		int l;
		int r;
		char s;

		sol(boolean st, int l, int r, char s) {
			this.st = st;
			this.l = l;
			this.r = r;
			this.s = s;
		}

		public String toString() {
			return st + " " + l + " " + r + " " + s;
		}
	}

	static class pair implements Comparable<pair> {
		int d;
		int t;

		pair(int d, int t) {
			this.d = d;
			this.t = t;
		}

		public String toString() {
			return d + " " + t;
		}

		public int compareTo(pair o) {
			if (o.d == d)
				return -o.t + t;
			return -o.d + d;
		}
	}

	static class unionfind {
		int[] p;
		int[] size;

		unionfind(int n) {
			p = new int[n];
			size = new int[n];

			for (int i = 0; i < n; i++) {
				p[i] = i;
			}
			Arrays.fill(size, 1);
		}

		int findSet(int v) {
			if (v == p[v])
				return v;
			return p[v] = findSet(p[v]);
		}

		boolean sameSet(int a, int b) {
			a = findSet(a);
			b = findSet(b);
			if (a == b)
				return true;
			return false;
		}

		int max() {
			int max = 0;
			for (int i = 0; i < size.length; i++)
				if (size[i] > max)
					max = size[i];
			return max;
		}

		void combine(int a, int b) {
			a = findSet(a);
			b = findSet(b);
			if (a == b)
				return;
			if (size[a] > size[b]) {
				p[b] = a;
				size[a] += size[b];

			} else {
				p[a] = b;
				size[b] += size[a];
			}
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}