#include <bits/stdc++.h>
using namespace std;
int p = 1e+9;
int memo[100005][105];
int candies(int n, int k, int a[], int j) {
  int ans = 0;
  if (j == n) {
    if (k == 0)
      return 1;
    else
      return 0;
  }
  if (memo[k][j] == -1) {
    for (int i = 0; i <= a[j]; i++) {
      ans = (ans % p + candies(n, k - i, a, j + 1) % p) % p;
    }
  } else
    return memo[k][j];
  memo[k][j] = ans % p;
  return ans;
}
int main() {
  int n, k;
  cin >> n >> k;
  int a[n + 5];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  memset(memo, -1, sizeof(memo));
  int ans = candies(n, k, a, 0);
  cout << ans << endl;
  return 0;
}
