#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e2;
const int MAXK = 1e5;
const int MOD = 1e9;
int n, k;
int a[MAXN];
int T[MAXN][MAXK];
int add(int f, int s) {
  f += s;
  return f % MOD;
}
int rec(int index, int rem) {
  if (index == n) {
    if (rem == 0)
      return 1;
    else
      return 0;
  }
  if (T[index][rem] != -1) {
    return T[index][rem];
  }
  int ans = 0;
  for (int i = 0; i <= a[index]; i++) {
    if (rem - i < 0) break;
    ans = add(ans, rec(index + 1, rem - i));
  }
  return ans;
}
void read_input() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
}
void solve() {
  memset(T, -1, sizeof(T));
  printf("%d\n", rec(0, k));
}
int main() {
  read_input();
  solve();
  return 0;
}
