#include <bits/stdc++.h>
using namespace std;
const long long mod = 1009;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const int FFT_MAXN = 262144;
const double pi = acos(-1.);
struct cp {
  double a, b;
  cp operator+(const cp &y) const { return (cp){a + y.a, b + y.b}; }
  cp operator-(const cp &y) const { return (cp){a - y.a, b - y.b}; }
  cp operator*(const cp &y) const {
    return (cp){a * y.a - b * y.b, a * y.b + b * y.a};
  }
  cp operator!() const { return (cp){a, -b}; };
} nw[FFT_MAXN + 1];
int bitrev[FFT_MAXN];
void dft(cp *a, int n, int flag = 1) {
  int d = 0;
  while ((1 << d) * n != FFT_MAXN) d++;
  for (int i = 0; i < n; i++)
    if (i < (bitrev[i] >> d)) swap(a[i], a[bitrev[i] >> d]);
  for (int l = 2; l <= n; l <<= 1) {
    int del = FFT_MAXN / l * flag;
    for (int i = 0; i < n; i += l) {
      cp *le = a + i, *ri = a + i + (l >> 1),
         *w = flag == 1 ? nw : nw + FFT_MAXN;
      for (int k = 0; k < l >> 1; k++) {
        cp ne = *ri * *w;
        *ri = *le - ne, *le = *le + ne;
        le++, ri++, w += del;
      }
    }
  }
  if (flag != 1)
    for (int i = 0; i < n; i++) a[i].a /= n, a[i].b /= n;
}
void fft_init() {
  int L = 0;
  while ((1 << L) != FFT_MAXN) L++;
  bitrev[0] = 0;
  for (int i = 1; i < FFT_MAXN; i++)
    bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1));
  for (int i = 0; i < FFT_MAXN + 1; i++)
    nw[i] = (cp){cos(2 * pi / FFT_MAXN * i), sin(2 * pi / FFT_MAXN * i)};
}
void convo(double *a, int n, double *b, int m, double *c) {
  static cp f[FFT_MAXN >> 1], g[FFT_MAXN >> 1], t[FFT_MAXN >> 1];
  int N = 2;
  while (N <= n + m) N <<= 1;
  for (int i = 0; i < N; i++)
    if (i & 1) {
      f[i >> 1].b = (i <= n) ? a[i] : 0.0;
      g[i >> 1].b = (i <= m) ? b[i] : 0.0;
    } else {
      f[i >> 1].a = (i <= n) ? a[i] : 0.0;
      g[i >> 1].a = (i <= m) ? b[i] : 0.0;
    }
  dft(f, N >> 1);
  dft(g, N >> 1);
  int del = FFT_MAXN / (N >> 1);
  cp qua = (cp){0, 0.25}, one = (cp){1, 0}, four = (cp){4, 0}, *w = nw;
  for (int i = 0; i < N >> 1; i++) {
    int j = i ? (N >> 1) - i : 0;
    t[i] =
        (four * !(f[j] * g[j]) - (!f[j] - f[i]) * (!g[j] - g[i]) * (one + *w)) *
        qua;
    w += del;
  }
  dft(t, N >> 1, -1);
  for (int i = 0; i < n + m + 1; i++)
    c[i] = (i & 1) ? t[i >> 1].a : t[i >> 1].b;
}
const int N = 401000;
int n, m, k, x, cnt[N];
double p[N], q[N], r[N];
vector<int> poly[N];
set<pair<int, int> > st;
vector<int> mul(vector<int> a, vector<int> b) {
  int n = ((int)(a).size()), m = ((int)(b).size());
  for (int i = 0; i < n; i++) p[i] = a[i];
  for (int i = 0; i < m; i++) q[i] = b[i];
  convo(p, n - 1, q, m - 1, r);
  vector<int> c(n + m - 1, 0);
  for (int i = 0; i < n + m - 1; i++) c[i] = (long long)(r[i] + 0.5) % mod;
  return c;
}
int main() {
  fft_init();
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    --x;
    cnt[x]++;
  }
  for (int i = 0; i < m; i++)
    if (cnt[i]) {
      poly[i] = vector<int>(cnt[i] + 1, 1);
      if (cnt[i]) st.insert(make_pair(cnt[i] + 1, i));
    }
  while (((int)(st).size()) > 1) {
    int u = st.begin()->second;
    st.erase(st.begin());
    int v = st.begin()->second;
    st.erase(st.begin());
    poly[m] = mul(poly[u], poly[v]);
    st.insert(make_pair(((int)(poly[m]).size()), m));
    m++;
  }
  printf("%d\n", poly[st.begin()->second][k]);
}
