#include <bits/stdc++.h>
using namespace std;
const int MX = 105, MK = 1e5 + 10, MOD = 1e9;
int a[MX];
long long dp[MX][MK], prefix[MX][MK];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = 0; i <= k; i++) prefix[0][i] = 1;
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      prefix[i][j + 1] = (prefix[i][j] + dp[i - 1][j]) % MOD;
    }
    for (int j = 0; j <= k; j++) {
      dp[i][j] = prefix[i][j + 1] - prefix[i][max(0, j - a[i])];
      dp[i][j] = (dp[i][j] + MOD) % MOD;
    }
  }
  printf("%lld\n", (dp[n][k] + MOD) % MOD);
  return 0;
}
