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 class Reader 
  { 
      final private int BUFFER_SIZE = 1 << 16; 
      private DataInputStream din; 
      private byte[] buffer; 
      private int bufferPointer, bytesRead; 

      public Reader() 
      { 
          din = new DataInputStream(System.in); 
          buffer = new byte[BUFFER_SIZE]; 
          bufferPointer = bytesRead = 0; 
      } 

      public Reader(String file_name) throws IOException 
      { 
          din = new DataInputStream(new FileInputStream(file_name)); 
          buffer = new byte[BUFFER_SIZE]; 
          bufferPointer = bytesRead = 0; 
      } 

      public String readLine() throws IOException 
      { 
          byte[] buf = new byte[64]; // line length 
          int cnt = 0, c; 
          while ((c = read()) != -1) 
          { 
              if (c == '\n') 
                  break; 
              buf[cnt++] = (byte) c; 
          } 
          return new String(buf, 0, cnt); 
      } 

      public int nextInt() throws IOException 
      { 
          int ret = 0; 
          byte c = read(); 
          while (c <= ' ') 
              c = read(); 
          boolean neg = (c == '-'); 
          if (neg) 
              c = read(); 
          do
          { 
              ret = ret * 10 + c - '0'; 
          }  while ((c = read()) >= '0' && c <= '9'); 

          if (neg) 
              return -ret; 
          return ret; 
      } 

      public long nextLong() throws IOException 
      { 
          long ret = 0; 
          byte c = read(); 
          while (c <= ' ') 
              c = read(); 
          boolean neg = (c == '-'); 
          if (neg) 
              c = read(); 
          do { 
              ret = ret * 10 + c - '0'; 
          } 
          while ((c = read()) >= '0' && c <= '9'); 
          if (neg) 
              return -ret; 
          return ret; 
      } 

      public double nextDouble() throws IOException 
      { 
          double ret = 0, div = 1; 
          byte c = read(); 
          while (c <= ' ') 
              c = read(); 
          boolean neg = (c == '-'); 
          if (neg) 
              c = read(); 

          do { 
              ret = ret * 10 + c - '0'; 
          } 
          while ((c = read()) >= '0' && c <= '9'); 

          if (c == '.') 
          { 
              while ((c = read()) >= '0' && c <= '9') 
              { 
                  ret += (c - '0') / (div *= 10); 
              } 
          } 

          if (neg) 
              return -ret; 
          return ret; 
      } 

      private void fillBuffer() throws IOException 
      { 
          bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
          if (bytesRead == -1) 
              buffer[0] = -1; 
      } 

      private byte read() throws IOException 
      { 
          if (bufferPointer == bytesRead) 
              fillBuffer(); 
          return buffer[bufferPointer++]; 
      } 

      public void close() throws IOException 
      { 
          if (din == null) 
              return; 
          din.close(); 
      } 
  } 

  // static final Scanner in = new Scanner(System.in);
  static final Reader in = new Reader();
  static final PrintWriter out = new PrintWriter(System.out);
  static int N, K;

  static int[] a;
  static long dp[][];
  static final int MOD = 1000000007;
  static long pre[][];

  public static void main(String[] args) throws Exception {
    N = in.nextInt();
    K = in.nextInt();
    a = new int[N];
    dp = new long[N + 1][K + 1];
    pre = new long[N+1][K+1];

    for (int i = 0; i < N; i++) {
      a[i] = in.nextInt();
      Arrays.fill(dp[i], -1);
      Arrays.fill(pre[i], -1);

    }
    Arrays.fill(dp[N], -1);
    Arrays.fill(pre[N], -1);  


    out.println(F(N-1, K));

    // out.println(Arrays.deepToString(dp));
    // out.println(Arrays.deepToString(pre));

    out.close();
  }

  static long F(int i, int k) {
    // System.out.println("\tat i == " + i + " k = " + k);
    if (i == 0) {
    //   System.out.println("\t\tat i == 0 k = "+k);
      if (k > a[0]) {
        // System.out.println("\t\treturning 0");
        dp[i][k] = 0;
        return 0;
      }
    //   System.out.println("\t\treturning 1"); 
      dp[i][k] = 1;
      return 1;
    }

    //..if value already exists return directly
    if (dp[i][k] != -1) return dp[i][k]; 

    //..start finding uncalculated part of prefix matrix
    int j;
    for(j = k;j >= 0;j--)
        if(pre[i-1][j] != -1) break;
    
    j++;

    //..start calculating the pre matrix 
    for(;j <= k;j++){
        if(j == 0) pre[i-1][j] = F(i-1,j)  % MOD;
        else
        pre[i-1][j] = (pre[i-1][j-1] + F(i-1,j)
        ) % MOD;
    }

    long val = pre[i-1][k]+MOD;

    if(k - a[i] > 0)
        val -= pre[i-1][k - a[i] - 1];
    val %= MOD;
    
    dp[i][k] = val;
    return dp[i][k];
  }
}
