#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++) {
    T[1][i] = 1;
  }
  int t = 1;
  int ans = 0;
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      for (int z = 0; z <= a[i]; z++) {
        T[i][j] = add(T[i][j], T[i - 1][j + z]);
      }
    }
    t ^= 1;
  }
  printf("%d\n", T[n][0]);
}
int main() {
  read_input();
  solve();
  return 0;
}
