#include <bits/stdc++.h>
using namespace std;
long long mod = 1009;
double PI = acos(-1);
int k;
int reverse(int num, int log_n) {
  int res = 0;
  for (int i = 0; i < log_n; i++)
    if ((1 << i) & num) res += (1 << (log_n - 1 - i));
  return res;
}
void fft(vector<complex<double> >& a, bool invert) {
  int n = a.size(), log_n = 0;
  while ((1 << log_n) < n) log_n++;
  for (int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) swap(a[i], a[j]);
  }
  double angle = 2 * PI / n * (invert ? -1 : 1);
  vector<complex<double> > root(n / 2);
  for (int i = 0; i < n / 2; i++)
    root[i] = complex<double>(cos(i * angle), sin(i * angle));
  for (int len = 2; len <= n; len <<= 1) {
    int step = n / len, aux = len / 2;
    for (int i = 0; i < n; i += len) {
      for (int j = 0; j < aux; j++) {
        complex<double> u = a[i + j], v = a[i + j + aux] * root[step * j];
        a[i + j] = u + v;
        a[i + j + aux] = u - v;
      }
    }
  }
  if (invert) {
    for (int i = 0; i < n; i++) a[i] /= n;
  }
}
void solve(vector<long long>& a, vector<long long>& b) {
  a.resize(min(int(a.size()), k + 1));
  b.resize(min(int(b.size()), k + 1));
  int n = 1, len = a.size() + b.size();
  while (n < len) n *= 2;
  a.resize(n);
  b.resize(n);
  vector<complex<double> > fft_a(a.begin(), a.end());
  fft(fft_a, 0);
  vector<complex<double> > fft_b(b.begin(), b.end());
  fft(fft_b, 0);
  vector<complex<double> > c(n);
  for (int i = 0; i < n; i++) c[i] = fft_a[i] * fft_b[i];
  fft(c, 1);
  for (int i = 0; i < n; i++) {
    a[i] = roundl(c[i].real());
    a[i] %= mod;
  }
  while (a.size() > 1 && a.back() == 0) a.pop_back();
}
int main() {
  int n, m;
  scanf("%d %d %d", &n, &m, &k);
  int len = 1;
  while (len < m) len *= 2;
  m = len;
  vector<int> freq(m);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    freq[x - 1]++;
  }
  vector<vector<long long> > torneio(m);
  for (int i = 0; i < m; i++)
    torneio[i] = vector<long long>(min(freq[i] + 1, k + 1), 1LL);
  for (int tam = 2; tam <= m; tam *= 2)
    for (int i = 0; i < m; i += tam) solve(torneio[i], torneio[i + tam / 2]);
  torneio[0].resize(k + 1);
  printf("%lld\n", torneio[0][k]);
  return 0;
}
