#include <bits/stdc++.h>
using namespace std;
const complex<double> I(0, 1);
const double PI = acos(-1.);
complex<double> cache[4194304];
complex<double> roots[19][262146];
complex<double> iroots[19][262146];
void _fft(complex<double> *a, int n, int w, int inv) {
  if (n == 1) return;
  for (int i = 0; i < n / 2; i++) {
    complex<double> s = a[i];
    complex<double> t = a[n / 2 + i];
    a[i] = s + t;
    a[n / 2 + i] = ((inv == 1) ? roots[w][i] : iroots[w][i]) * (s - t);
  }
  _fft(a, n / 2, w - 1, inv);
  _fft(a + n / 2, n / 2, w - 1, inv);
  for (int i = 0; i < n / 2; i++) cache[i] = a[i];
  for (int i = 0; i < n / 2; i++) a[2 * i + 1] = a[n / 2 + i];
  for (int i = 0; i < n / 2; i++) a[2 * i] = cache[i];
}
void fft(vector<complex<double>> &a) {
  complex<double> w = exp(2 * PI * I / (double)a.size());
  _fft(&a[0], a.size(), log2(a.size()), 1);
}
void ifft(vector<complex<double>> &a) {
  complex<double> w = exp(-2 * PI * I / (double)a.size());
  _fft(&a[0], a.size(), log2(a.size()), -1);
  for (int i = 0; i < a.size(); i++) a[i] /= a.size();
}
vector<long long> multiply(vector<long long> &a, vector<long long> &b) {
  int n = (1 << (int)ceil(log2(a.size() + b.size() - 1)));
  vector<complex<double>> ca(n, 0);
  vector<complex<double>> cb(n, 0);
  for (int i = 0; i < a.size(); i++) ca[i] = a[i];
  for (int i = 0; i < b.size(); i++) cb[i] = b[i];
  fft(ca);
  fft(cb);
  for (int i = 0; i < n; i++) ca[i] *= cb[i];
  ifft(ca);
  vector<long long> result(a.size() + b.size() - 1);
  for (int i = 0; i < result.size(); i++) {
    result[i] = round(ca[i].real());
  }
  return result;
}
int main() {
  ios_base::sync_with_stdio(false);
  for (int i = 0; i <= 18; i++) {
    for (int j = 0; j <= (1 << i); j++) {
      roots[i][j] = exp(2 * j * PI * I / (double)(1 << i));
      iroots[i][j] = exp(-2 * j * PI * I / (double)(1 << i));
    }
  }
  int n, m, k;
  map<int, int> colors;
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    int color;
    cin >> color;
    colors[color]++;
  }
  auto comp = [](const vector<long long> &a, const vector<long long> &b) {
    return a.size() > b.size();
  };
  priority_queue<vector<long long>, vector<vector<long long>>, decltype(comp)>
      pq(comp);
  for (auto color : colors) {
    vector<long long> poly(color.second + 1, 1);
    pq.push(poly);
  }
  while (pq.size() > 1) {
    vector<long long> a = pq.top();
    pq.pop();
    vector<long long> b = pq.top();
    pq.pop();
    vector<long long> c = multiply(a, b);
    for (int i = 0; i < c.size(); i++) c[i] %= 1009LL;
    pq.push(c);
  }
  auto result = pq.top();
  cout << result[k] << "\n";
  return 0;
}
