#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
using pii = pair<int, int>;
using cd = complex<ld>;
constexpr int LOG = 20;
constexpr int N = 1 << LOG;
const ld PI = acos(-1);
int inv[N + 10];
cd w[N + 10];
cd A[N + 10];
cd B[N + 10];
void precalc() {
  for (int i = 0; i < N; i++) {
    ld ang = 2 * PI * i / N;
    w[i] = cd(cos(ang), sin(ang));
  }
  for (int i = 1; i < N; i++) {
    inv[i] = (inv[i >> 1] >> 1) | ((i & 1) << (LOG - 1));
  }
}
void fft(cd *A, int n) {
  int n_log = __builtin_ctz(n);
  for (int i = 0; i < n; i++) {
    int inv_shift = inv[i] >> (LOG - n_log);
    if (i < inv_shift) {
      swap(A[i], A[inv_shift]);
    }
  }
  for (int lvl = 0; lvl < n_log; lvl++) {
    int len = 1 << lvl;
    for (int i = 0; i < n; i += 2 * len) {
      for (int j = 0; j < len; j++) {
        cd x = A[i + j], y = A[i + j + len] * w[j << (LOG - 1 - lvl)];
        A[i + j] = x + y;
        A[i + j + len] = x - y;
      }
    }
  }
}
int cnt[N + 10];
vector<int> polys[N + 10];
void mupltiply(vector<int> &a, vector<int> &b) {
  int len = 1;
  while (len < a.size() + b.size()) {
    len <<= 1;
  }
  a.resize(len, 0);
  b.resize(len, 0);
  for (int i = 0; i < len; i++) {
    A[i] = a[i];
    B[i] = b[i];
  }
  fft(A, len);
  fft(B, len);
  for (int i = 0; i < len; i++) {
    A[i] *= B[i];
  }
  fft(A, len);
  reverse(A + 1, A + len);
  for (int i = 0; i < len; i++) {
    ll t = round(A[i].real() / len);
    t = (t % 1009 + 1009);
    if (t >= 1009) {
      t -= 1009;
    }
    a[i] = (int)t;
  }
  while (a.back() == 0) {
    a.pop_back();
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  precalc();
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  for (int i = 0; i <= m; i++) {
    polys[i] = vector<int>(cnt[i] + 1, 1);
  }
  for (int len = 1; len < m + 1; len <<= 1) {
    for (int i = 0; i <= m; i += 2 * len) {
      int j = i + len;
      if (j > m || (len == 1 && cnt[j] == 0)) {
        continue;
      }
      mupltiply(polys[i], polys[j]);
    }
  }
  cout << polys[0][k];
  return 0;
}
