#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> a;
int dp[100001];
int main() {
  cin >> n >> k;
  for (int i = 0; i < k + 1; ++i) dp[i] = 0;
  dp[0] = 1;
  for (int i = 0; i < n; ++i) {
    int ai;
    cin >> ai;
    int left = k - min(ai, k);
    int right = k + 1;
    int sm = 0;
    for (int j = left; j < right; ++j) {
      sm = (sm + dp[j]) % 1000000009;
    }
    while (right > 0) {
      int tmp = dp[right - 1];
      dp[right - 1] = sm;
      if (left > 0) {
        left--;
        sm = (sm + dp[left]) % 1000000009;
      }
      right--;
      sm = (sm - tmp) % 1000000009;
      if (sm < 0) sm += 1000000009;
    }
  }
  cout << dp[k] << endl;
}
