#include <bits/stdc++.h>
using namespace std;
const long long N = 1 << 18;
const long long mod = 1009;
const double pi = acos(-1);
vector<complex<double> > w(N), p;
long long c[N], n, m, k;
long long revbit(long long nbit, long long mask) {
  for (long long i = 0, j = nbit - 1; i < j; ++i, --j)
    if ((mask >> i & 1) != (mask >> j & 1)) {
      mask ^= (1 << i);
      mask ^= (1 << j);
    }
  return mask;
}
void FFT(long long n, vector<complex<double> >& a, bool inv) {
  if (n == 1) return;
  for (long long i = 0; i < n; ++i) {
    long long j = revbit(log2(n), i);
    if (i < j) swap(a[i], a[j]);
  }
  vector<complex<double> > anex(n);
  for (long long k = 1; k < n; k <<= 1) {
    double alp = pi / k;
    if (inv) alp = -alp;
    complex<double> W(1), u(cos(alp), sin(alp));
    for (long long i = 0; i < k; ++i) w[i] = W, W *= u;
    long long even = 0, odd = k;
    while (even < n) {
      for (long long i = 0; i < k; ++i) {
        anex[even + i] = a[even + i] + w[i] * a[odd + i];
        anex[odd + i] = a[even + i] - w[i] * a[odd + i];
      }
      even += 2 * k;
      odd += 2 * k;
    }
    for (long long i = 0; i < n; ++i) a[i] = anex[i];
  }
  if (inv)
    for (long long i = 0; i < n; ++i) a[i] /= n;
}
void solve(long long l, long long r, vector<complex<double> >& P) {
  long long sz = c[r] - c[l - 1];
  long long j = log2(sz) + 1;
  if (l == r) {
    complex<double> W(1);
    for (long long i = 0; i <= sz; ++i) P[i] = W;
    return;
  }
  vector<complex<double> > Q;
  Q.resize(1 << j);
  long long be = l, en = r;
  while (be != en) {
    long long mi = (be + en) / 2;
    if (c[mi] - c[l - 1] >= sz / 2)
      en = mi;
    else
      be = mi + 1;
  }
  solve(l, be, P);
  solve(be + 1, r, Q);
  FFT(1 << j, P, 0);
  FFT(1 << j, Q, 0);
  for (long long i = 0; i < (1 << j); ++i) P[i] = P[i] * Q[i];
  FFT(1 << j, P, 1);
  for (long long i = 0; i < (1 << j); ++i) {
    long long k = P[i].real() / mod;
    k *= mod;
    k = round(P[i].real() - k);
    P[i] = k;
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  scanf("%d%d%d", &n, &m, &k);
  fill(c + 1, c + 1 + m, 0);
  for (long long i = 1; i <= n; ++i) {
    long long x;
    scanf("%d", &x);
    c[x]++;
  }
  sort(c + 1, c + 1 + m);
  for (long long i = 1; 2 * i <= m; ++i) swap(c[i], c[m + 1 - i]);
  m = 0;
  while (c[m + 1] > 0) m++;
  for (long long i = 2; i <= m; ++i) c[i] += c[i - 1];
  long long j = log2(c[m]) + 1;
  p.resize(1 << j);
  solve(1, m, p);
  long long ans = p[k].real();
  ans %= mod;
  ans += (ans < 0 ? mod : 0);
  cout << ans << endl;
}
