#include <bits/stdc++.h>
using namespace std;
long long n, k;
long long dp[101][100005];
long long candies[100005];
long long solve(long long i, long long k) {
  if (i == n && k == 0) return 1;
  if (i >= n || k < 0 || (i >= n && k > 0)) return 0;
  if (dp[i][k] != -1) return dp[i][k];
  long long ans = 0;
  for (int j = 0; j <= candies[i]; j++) {
    ans = (ans + solve(i + 1, k - j)) % 1000000009;
  }
  dp[i][k] = ans % 1000000009;
  return dp[i][k];
}
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> candies[i];
  ;
  memset(dp, -1, sizeof(dp));
  cout << solve(0, k) << endl;
  return 0;
}
