#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e2;
const int MAXK = 1e5 + 5;
const int MOD = 1e9;
const int TSIZE = (1 << 17);
int n, k;
int a[MAXN];
int T[MAXN][MAXK];
int tree[TSIZE][2];
int add(int f, int s) {
  f += s;
  return f % MOD;
}
int get_index(int index) { return (TSIZE >> 1) + index; }
void update(int index, int value, int s) {
  index = get_index(index);
  tree[index][s] = value;
  for (int i = index >> 1; i > 0; i >>= 1) {
    tree[i][s] = add(tree[i * 2][s], tree[i * 2 + 1][s]);
  }
}
int query(int l, int r, int s) {
  l = get_index(l);
  r = get_index(r);
  if (l == r) {
    return tree[l][s];
  }
  int ans = add(tree[l][s], tree[r][s]);
  while (l + 1 != r) {
    if ((l & 1) == 0) ans = add(ans, tree[l + 1][s]);
    if ((r & 1) == 1) ans = add(ans, tree[r - 1][s]);
    l >>= 1;
    r >>= 1;
  }
  return ans;
}
void read_input() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
}
void solve() {
  for (int i = 0; i <= a[0]; i++) {
    update(k - i, 1, 0);
  }
  int t = 1;
  int ans = 0;
  for (int i = 2; i <= n; i++, t ^= 1) {
    for (int j = 0; j <= k; j++) {
      int right = min(k, a[i] + k);
      int temp = query(0, right, t ^ 1);
      ans = temp;
      update(j, temp, t);
    }
    for (int i = 0; i <= TSIZE; i++) {
      tree[i][t ^ 1] = 0;
    }
  }
  printf("%d\n", query(0, 0, t ^ 1));
}
int main() {
  read_input();
  solve();
  return 0;
}
