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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static final int mod = (int) (1e9 + 7);

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner();
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = sc.nextInt();
        if (k == 0) out.println(1);
        else {
            int[][] memo = new int[n + 1][k + 1];
            Arrays.fill(memo[n], 1);
            for (int i = n - 1; i >= 0; i--) {
                for (int rem = k; rem >= 0; rem--) {
                    memo[i][rem] = memo[i + 1][rem];
                    if (rem - a[i] - 1 >= 0) memo[i][rem] = add(memo[i][rem], -memo[i + 1][rem - a[i] - 1]);
                }
                for (int rem = 1; rem <= k; rem++)
                    memo[i][rem] = add(memo[i][rem], memo[i][rem - 1]);
            }
            out.println(add(memo[0][k], -memo[0][k - 1]));
        }
        out.flush();
        out.close();
    }

    static int add(int a, int b) {
        long c = a + b;
        if (c >= mod) c -= mod;
        if (c < 0) c += mod;
        return (int) c;
    }


    static class Scanner {
        BufferedReader br;
        StringTokenizer st;

        Scanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

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

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