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


class Main {
    static final long MOD = 1000000007;

    // Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
    public static void main(String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        long N;
        N = sc.nextLong();
        long K;
        K = sc.nextLong();
        long[] a = new long[(int)(N)];
        for(int i = 0 ; i < N ; i++){
                a[i] = sc.nextLong();
        }
        solve2(N, K, a);
    }

    static void solve(long N, long K, long[] a){
        long[][] dp = new long[(int)N][(int)(K+1)];
        
        for (int i = 0; i <= a[0]; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < N; i++){
            for (int j = 0; j <= K; j++){
                long sum = 0;
                for (int k = 0; k <= a[i]; k++){
                    if (j >= k){
                        sum = (sum + dp[i-1][j-k]) % MOD;
                    }
                }
                dp[i][j] = sum;
            }
        }

        System.out.print(dp[(int)(N-1)][(int)(K)]);
    }

    static long add(long a, long b){
        return (a + b) % MOD;
    }

    static long minus(long a, long b){
        long rst;
        rst = a - b;
        if (rst < 0) rst += MOD;
        return rst;
    }

    // optimize with prifix sum
    static void solve2(long N, long K, long[] a){
        long[][] dp = new long[(int)N][(int)(K+1)];
        long[][] prefix = new long[(int)N][(int)(K+1)];
        
        for (int i = 0; i <= a[0]; i++){
            dp[0][i] = 1;
            prefix[0][i] = i > 0 ? (prefix[0][i-1] + 1) : 1;
        }
        for (int i = (int)a[0] + 1; i <= K; i++){
            prefix[0][i] = prefix[0][i-1];
        }

        for (int i = 1; i < N; i++){
            for (int j = 0; j <= K; j++){
                if (j-(int)(a[i])-1 >= 0){
                    dp[i][j] = minus(prefix[i-1][j], prefix[i-1][j-(int)a[i]-1]);
                }else{
                    dp[i][j] = prefix[i-1][j];
                }

                prefix[i][j] = j > 0 ? add(prefix[i][j-1], dp[i][j]) : dp[i][j];
            }
        }

        System.out.print(dp[(int)(N-1)][(int)(K)]);
    }
}
