#include <bits/stdc++.h>
using namespace std;
int N, M, K, a[200009];
struct base {
  double x, y;
  base() : x(0), y(0) {}
  base(double a, double b = 0) : x(a), y(b) {}
  base operator/=(double k) {
    x /= k;
    y /= k;
    return (*this);
  }
  base operator*(base a) const {
    return base(x * a.x - y * a.y, x * a.y + y * a.x);
  }
  base operator*=(base a) {
    double tx = x * a.x - y * a.y;
    double ty = x * a.y + y * a.x;
    x = tx;
    y = ty;
    return (*this);
  }
  base operator+(base a) const { return base(x + a.x, y + a.y); }
  base operator-(base a) const { return base(x - a.x, y - a.y); }
  double real() { return x; }
  double imag() { return y; }
};
void fft(vector<base> &a, bool invert) {
  int n = (int)a.size();
  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]);
  }
  for (int len = 2; len <= n; len <<= 1) {
    double ang = 2 * acos(-1) / len * (invert ? -1 : 1);
    base wlen(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      base w(1);
      for (int j = 0; j < len / 2; ++j) {
        base u = a[i + j], v = a[i + j + len / 2] * w;
        a[i + j] = u + v;
        a[i + j + len / 2] = u - v;
        w *= wlen;
      }
    }
  }
  if (invert)
    for (int i = 0; i < n; ++i) a[i] /= n;
}
void convolution(vector<base> &a, vector<base> &b, vector<base> &res) {
  int n = 1;
  while (n < a.size() + b.size() - 1) n <<= 1;
  a.resize(n), b.resize(n);
  fft(a, false);
  fft(b, false);
  res.resize(n);
  for (int i = 0; i < n; ++i) res[i] = a[i] * b[i];
  fft(res, true);
  for (int i = 0; i < n; ++i)
    res[i] = (long long int)round(res[i].real()) % 1009;
}
vector<vector<base> > A;
vector<base> b;
void solve() {
  vector<vector<base> > res;
  while ((int)A.size() > 1) {
    for (int i = 0; i < (int)A.size() - 1; i += 2) {
      convolution(A[i], A[i + 1], b);
      res.push_back(b);
    }
    if (A.size() % 2) res.push_back(A[A.size() - 1]);
    A = res;
    res.clear();
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  vector<int> vals;
  cin >> N >> M >> K;
  for (int i = 0; i < N; ++i) cin >> a[i];
  sort(a, a + N);
  for (int i = 0; i < N; ++i) {
    int u = a[i];
    int qty = 0;
    while (i < N && a[i] == u) ++qty, ++i;
    --i;
    vals.push_back(qty + 1);
  }
  sort(vals.begin(), vals.end());
  for (int i : vals) {
    b.assign(i, base(1));
    A.push_back(b);
  }
  solve();
  cout << round(A[0][K].real()) << '\n';
}
