#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int cnt[200005];
int n, m, k;
vector<unsigned long long> polys[200005];
struct cmp {
  bool operator()(int a, int b) const {
    return polys[a].size() > polys[b].size();
  }
};
priority_queue<int, vector<int>, cmp> q;
const int NMAX = 1 << 19;
const double PI = 2 * acos(0.0);
struct FFT {
  vector<int> rev;
  vector<complex<double> > omega, oinv;
  int K, N;
  FFT(int k) {
    K = k;
    N = 1 << k;
    rev.resize(N);
    omega.resize(N);
    oinv.resize(N);
    for (int i = 0; i < (N); i++) {
      rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (K - 1));
      omega[i] = polar(1.0, 2.0 * PI / N * i);
      oinv[i] = conj(omega[i]);
    }
  }
  void dft(complex<double>* a, vector<complex<double> >& w) {
    for (int i = 0; i < (N); i++)
      if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int l = 2; l <= N; l *= 2) {
      int m = l / 2;
      for (complex<double>* p = a; p != a + N; p += l)
        for (int k = 0; k < (m); k++) {
          complex<double> t = w[N / l * k] * p[k + m];
          p[k + m] = p[k] - t;
          p[k] += t;
        }
    }
  }
  void fft(complex<double>* a) { dft(a, omega); }
  void ifft(complex<double>* a) {
    dft(a, oinv);
    for (int i = 0; i < (N); i++) a[i] /= N;
  }
  void conv(complex<double>* a, complex<double>* b) {
    fft(a);
    fft(b);
    for (int i = 0; i < (N); i++) a[i] *= b[i];
    ifft(a);
  }
};
vector<FFT> fft;
int roundup(int x) {
  while (x & (x - 1)) x += x & (-x);
  return x;
}
void mul(vector<unsigned long long>& a, vector<unsigned long long>& b) {
  int maxsz = a.size() + b.size();
  int sz = roundup(maxsz);
  a.resize(sz);
  b.resize(sz);
  static complex<double> aa[1 << 20], bb[1 << 20];
  for (int i = 0; i < sz; i++) {
    aa[i] = a[i];
    bb[i] = b[i];
  }
  fft[__builtin_ctz(sz) - 1].conv(aa, bb);
  a.resize(maxsz);
  for (int i = 0; i < maxsz; i++) {
    a[i] = real(aa[i]) + 0.5;
    a[i] %= 1009;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (int i = 1; i <= 19; i++) fft.push_back(FFT(i));
  cin >> n >> m >> k;
  for (int i = 0; i < (n); i++) {
    int v;
    cin >> v;
    cnt[v]++;
  }
  for (int i = 1; i <= (m); i++) {
    if (cnt[i]) {
      polys[i].resize(cnt[i] + 1);
      fill((polys[i]).begin(), (polys[i]).end(), 1);
      q.push(i);
    }
  }
  while (q.size() > 1) {
    int a = q.top();
    q.pop();
    int b = q.top();
    q.pop();
    mul(polys[a], polys[b]);
    q.push(a);
  }
  vector<unsigned long long>& res = polys[q.top()];
  cout << res[k] << endl;
  return 0;
}
