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 {
    private final 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 int dp[][];
  static final int MOD = 1000000007;
  static int pre[][];

  public static void main(String[] args) throws Exception {
    N = in.nextInt();
    K = in.nextInt();
    a = new int[N];
    dp = new int[N + 1][K + 1];
    pre = new int[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);
    F();
    out.println(dp[N - 1][K]);

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

    out.close();
  }

  static void F() {

    //..base case
    dp[0][0] = 1;
    pre[0][0] = 1;
    for (int k = 1; k <= K; k++) {

      if (a[0] >= k) 
        dp[0][k] = 1; 
      else 
        dp[0][k] = 0;

      pre[0][k] = pre[0][k - 1] + dp[0][k];
    }

    for (int i = 1; i < N; i++) {
      for (int k = 0; k <= K; k++) {
        
        int 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;

        //..calculate the prefix sum for cell (i,k)
        pre[i][k] = dp[i][k];
        if(k > 0)
          pre[i][k]  += pre[i][k-1];

        pre[i][k] %= MOD;  
      }
    }
   
  }
}
