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.util.Arrays;
import java.util.Scanner;

public class Main {

	static final int DIVIDE_NUMBER = 1000000007;

	static int childrenCount;
	static int candyCount;
	static int[] childCapacityArray;
	static long[][] dp;

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		childrenCount = scan.nextInt();
		candyCount = scan.nextInt();
		scan.nextLine();

		childCapacityArray = Arrays.stream(scan.nextLine().split(" "))
				.mapToInt(Integer::parseInt)
				.toArray();

		dp = new long[childrenCount + 1][candyCount + 1];

		for (int n = 0; n < childrenCount + 1; n++) {

			for (int k = 0; k < candyCount + 1; k++) {

				dpMethod(n, k);
			}
		}

		println(dp[childrenCount][candyCount]);
	}

	public static void dpMethod(int n, int k) {

		if (k == 0) {

			dp[n][k] = 1;

		} else if (n == 0) {

			dp[n][k] = 0;

		} else {

			long outOfScope = k < childCapacityArray[n - 1] + 1
					? 0
					: dp[n - 1][k - childCapacityArray[n - 1] - 1];

			dp[n][k] = modulo(dp[n - 1][k] + dp[n][k - 1] - outOfScope + DIVIDE_NUMBER);
		}

	}

	public static long modulo(long target) {

		return target % DIVIDE_NUMBER;
	}

	public static void println(Object target) {
		System.out.println(target);
	}
}
