#include <bits/stdc++.h>
using namespace std;
const int DFT = 1;
const int IDFT = -1;
const int maxn = 2e5 + 5;
const int lim = 1 << 19;
const double PI = acos(-1.0);
const int mod = 1009;
struct Complex {
  double x, y;
  Complex(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};
Complex operator+(Complex a, Complex b) {
  return Complex(a.x + b.x, a.y + b.y);
}
Complex operator-(Complex a, Complex b) {
  return Complex(a.x - b.x, a.y - b.y);
}
Complex operator*(Complex a, Complex b) {
  return Complex(a.x * b.x - a.y * b.y, a.x * b.y + b.x * a.y);
}
int rev[lim];
void FFT(Complex *a, int len, int opt) {
  for (int i = 0; i < len; i++)
    if (i > rev[i]) swap(a[i], a[rev[i]]);
  for (int i = 1; i < len; i <<= 1) {
    int step = i << 1;
    Complex wn = Complex(cos(PI / i), opt * sin(PI / i));
    for (int j = 0; j < len; j += step) {
      Complex w = Complex(1, 0);
      for (int k = 0; k < i; k++, w = w * wn) {
        Complex x = a[j + k];
        Complex y = w * a[i + j + k];
        a[j + k] = x + y;
        a[i + j + k] = x - y;
      }
    }
  }
  if (opt == DFT) return;
  for (int i = 0; i < len; i++) a[i].x /= len;
}
void calc(Complex *a, int n, Complex *b, int m) {
  int bln = 1, bct = 0;
  while (bln < (n + m)) bln <<= 1, bct++;
  for (int i = 0; i < bln; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bct - 1));
  FFT(a, bln, DFT);
  FFT(b, bln, DFT);
  for (int i = 0; i < bln; i++) a[i] = a[i] * b[i];
  FFT(a, bln, IDFT);
}
vector<int> f[maxn];
int D[22][2][lim];
int cdq(int dep, int l, int r, int isleft) {
  static Complex tf[lim];
  static Complex tg[lim];
  if (l == r) {
    for (int i = 0; i < f[l].size(); i++) D[dep][isleft][i] = f[l][i];
    return f[l].size();
  }
  int mid = (l + r) >> 1;
  int lsz = cdq(dep + 1, l, mid, 0);
  int rsz = cdq(dep + 1, mid + 1, r, 1);
  int deg = max(lsz, rsz);
  int bln = 1;
  while (bln < deg + deg) bln <<= 1;
  for (int i = 0; i < bln; i++) tf[i] = Complex(1.0 * D[dep + 1][0][i], 0);
  for (int i = 0; i < bln; i++) tg[i] = Complex(1.0 * D[dep + 1][1][i], 0);
  calc(tf, deg, tg, deg);
  for (int i = 0; i < bln; i++)
    D[dep][isleft][i] = (long long)(tf[i].x + 0.5) % mod;
  int sz = bln;
  while (sz && D[dep][isleft][sz - 1] == 0) sz--;
  for (int i = 0; i < bln; i++) D[dep + 1][0][i] = D[dep + 1][1][i] = 0;
  return sz;
}
int c[maxn];
int main(void) {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
  sort(c + 1, c + 1 + n);
  int cnt = 0;
  for (int i = 1, j; i <= n; i = j + 1) {
    j = i;
    while (j + 1 <= n && c[j + 1] == c[i]) j++;
    ++cnt;
    for (int K = 0; K <= j - i + 1; K++) {
      f[cnt].push_back(1);
    }
  }
  int sz = cdq(0, 1, cnt, 0);
  if (k < sz)
    printf("%d\n", D[0][0][k]);
  else
    printf("0\n");
  return 0;
}
