#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MOD = 1000000009;

// 入力
int n, A,m;
A=0;
scanf("%d",&n);
int a[n];
for(m=0;m++-n;)scanf("%d",&d[m]);


// DPテーブル
int dp[110][10010];

int main() {
    cin >> n >> A;
    for (int i = 0; i < n; ++i) cin >> a[i];

    memset(dp, 0, sizeof(dp));   // 一旦すべて 0 に
    dp[0][0] = 1;                // dp[0][0] だけ 1 に

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= A; ++j) {
            (dp[i+1][j] += dp[i][j]) %= MOD;
            if (j >= a[i]) (dp[i+1][j] += dp[i][j-a[i]]) %= MOD;
        }
    }

    cout << dp[n][A] << endl;
}
