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


public class Main {
    static int mod = (int)1e9+7;
    public static void main(String[] args) {

        FastReader f = new FastReader();
        int n =f.nextInt();
        int k = f.nextInt();
        int candies [] = new int[n];
        for(int i=0;i<n;i++)
            candies[i] =f.nextInt();
        System.out.println(solve(candies,n,k));



    }

    static int solve(int[] candies ,int n,int k)
    {
        int dp[][] = new int[n+1][k+1];
        dp[0][0] =1;
        int[] ways  =new int[k+1];

        for(int i=1;i<=n;i++) {
            dp[i][0]=1;
        }

        for(int i=1;i<=n;i++)
        {
            ways[0] =dp[i-1][0];
            for(int j=1;j<=k;j++)
            {
                ways[j] =  ways[j-1]+dp[i-1][j];
                if (ways[j] >mod)
                    ways[j]-=mod;
            }
            for(int j=1;j<=k;j++)
            {
                 dp[i][j] += ways[j]-((j-candies[i-1]-1) >=0?ways[j-candies[i-1]-1]:0);
                 if (dp[i][j]<0)
                     dp[i][j]+=mod;
            }
        }
//        for(int i=0;i<=n;i++)
//        {
//            System.out.println();
//            for(int j=0;j<=k;j++)
//            {
//                System.out.print(dp[i][j]+" ");
//            }
//
//        }


        return dp[n][k];
    }




    static  class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

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

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}
