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

public class Main {

    static StreamTokenizer in;

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws Exception {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int n = nextInt();
        int k = nextInt();

        int[] candies = new int[n];

        for (int i = 0; i < n; i++) {
            candies[i] = nextInt();
        }

        int[] dp = new int[k + 1];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            int up_to = candies[i];
            int[] prefixArray = new int[k+1];
            for (int used = k; used >= 0; used--) {
                int temp = dp[used];
                int L = used + 1;
                int R = used + Math.min(up_to, k - used);

                if (L <= R) {
                    prefixArray[L] = add_self(prefixArray[L], temp);

                    if (R + 1 <= k) {
                        prefixArray[R + 1] = remove_self(prefixArray[R + 1], temp);
                    }
                }
            }

            int prefix = 0;
            for (int j = 0; j <= k; j++) {
                prefix = add_self(prefix, prefixArray[j]);
                dp[j] = add_self(dp[j], prefix);
            }
        }

        out.println(dp[k]);

        out.close();
    }

    static int mod = 1000000007;

    static int add_self(int a, int b) {
        a += b;
        if (a >= mod) a -= mod;

        return a;
    }
    static int remove_self(int a, int b) {
        a -= b;
        if (a < 0) a += mod;

        return a;
    }
}