#include <bits/stdc++.h>
using namespace std;
struct cplx {
  long double r, i;
  cplx(long double ir = 0.0, long double ii = 0.0) { r = ir, i = ii; }
  cplx operator+(const cplx &y) { return cplx(r + y.r, i + y.i); }
  cplx operator-(const cplx &y) { return cplx(r - y.r, i - y.i); }
  cplx operator*(const cplx &y) {
    return cplx(r * y.r - i * y.i, r * y.i + i * y.r);
  }
};
const long double Pi = acos(-1.0);
long long n, m, k;
long long cnt[200200];
vector<vector<long long> > pol;
set<pair<int, int> > all;
cplx x1[1 << 20], x2[1 << 20];
void change(cplx *y, int ln) {
  for (int i = 1, j = ln >> 1; i < ln - 1; i++) {
    if (i < j) swap(y[i], y[j]);
    int k = ln >> 1;
    while (j >= k) {
      j -= k;
      k >>= 1;
    }
    j += k;
  }
}
void fft(cplx *y, int on, int len) {
  change(y, len);
  for (int m = 2; m <= len; m <<= 1) {
    cplx wm(cos(-on * 2 * Pi / m), sin(-on * 2 * Pi / m));
    for (int k = 0; k < len; k += m) {
      cplx w(1, 0);
      for (int j = 0; j < m / 2; j++) {
        cplx u = y[k + j];
        cplx t = w * y[k + j + m / 2];
        y[k + j] = u + t;
        y[k + j + m / 2] = u - t;
        w = w * wm;
      }
    }
  }
  if (on == -1)
    for (int i = 0; i < len; i++) y[i].r = y[i].r / len;
}
void mult(vector<long long> &a, vector<long long> &b, vector<long long> &res) {
  int len = 1, la = a.size(), lb = b.size();
  while (len < la + lb) len <<= 1;
  for (int i = 0; i < la; i++) x1[i] = cplx(a[i], 0);
  for (int i = la; i < len; i++) x1[i] = cplx(0, 0);
  for (int i = 0; i < lb; i++) x2[i] = cplx(b[i], 0);
  for (int i = lb; i < len; i++) x2[i] = cplx(0, 0);
  fft(x1, 1, len);
  fft(x2, 1, len);
  for (int i = 0; i < len; i++) x1[i] = x1[i] * x2[i];
  fft(x1, -1, len);
  res.resize(min((long long)len, k + 1));
  for (int i = 0; i < res.size(); i++) {
    res[i] = x1[i].r + 0.5;
    res[i] %= 1009;
  }
}
int main() {
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    cnt[x]++;
  }
  for (int i = 1; i <= m; i++) {
    if (cnt[i] == 0) continue;
    pol.push_back(vector<long long>(cnt[i] + 1, 1ll));
    all.insert({pol.back().size(), pol.size() - 1});
  }
  while (all.size() > 1) {
    int x = all.begin()->second;
    all.erase(all.begin());
    int y = all.begin()->second;
    all.erase(all.begin());
    mult(pol[x], pol[y], pol[x]);
    all.insert({pol[x].size(), x});
  }
  cout << pol[all.begin()->second][k] << endl;
  return 0;
}
