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 {
    void run() {
        Scanner sc = new Scanner(System.in);
        long MOD = (long) 1e9 + 7;
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        // dp[i][j] .. i番目の子供でj個の飴を分け合う方法の総数
        long[][] dp = new long[N + 1][K + 1];

        dp[0][0] = 1;

        for (int i = 0; i < N; i++) { // 10 ^ 2
            long[] cum = new long[K + 2];
            cum[0] = dp[i][0];
            for (int j = 0; j <= K; j++) {
                cum[j + 1] = (cum[j] + dp[i][j]) % MOD;
            }
//            debug(cum);
            for (int j = 0; j <= K; j++) {
                dp[i + 1][j] = (cum[j + 1] - cum[Math.max(0, j - arr[i])] + MOD) % MOD;
            }

            // これはTLE
//            for (int j = 1; j <= K; j++) { // 10 ^ 5
//                for (int k = 0; k <= arr[i]; k++) { // 10 ^ 5
//                    if (j - k >= 0) {
//                        dp[i + 1][j] += dp[i][j - k] % MOD;
//                    }
//                }
//            }

//            // これがダメな理由がいまいちわからん
//            for (int j = 1; j <= Math.min(sum, K); j++) { // 10 ^ 5
//                if (j - arr[i] >= 0) {
//                    // dp[i + 1][j] = dp[i][j] + dp[i][j - 1] + ... + dp[i][j - arr[i]];
//                    // dp[i + 1][j - 1] = dp[i][j - 1] + dp[i][j - 2] + ... + dp[i][j - arr[i] - 1];
//                    // 両辺引いて：
//                    dp[i + 1][j] = (dp[i][j] + dp[i][j - 1] - dp[i][j - arr[i] - 1]) % MOD;
//                } else {
//                    // dp[i + 1][j] = dp[i][j] + dp[i][j - 1] + ... + dp[i][0];
//                    // dp[i + 1][j - 1] = dp[i][j - 1] + dp[i][j - 2] + ... + dp[i][0];
//                    dp[i + 1][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
//                }
//            }
        }
        System.out.println(dp[N][K] % MOD);
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}
