#include <bits/stdc++.h>
using namespace std;
using point = complex<double>;
const long double pi = acosl(-1);
point prep[1100007];
point v[2][1100007];
vector<point> dft(vector<point> P, int w) {
  int k = round(log2(P.size()));
  int n = P.size();
  prep[0] = 1;
  for (int i = 1; i <= n; i++)
    prep[i] = point(cos(pi * 2. / n * i), sin(pi * 2. / n * i) * w);
  for (int i = 0; i < n; i++) v[0][i] = P[i];
  for (int l = 1, jump = n / 2; l <= k; l++, jump /= 2)
    for (int pol = 0; pol < jump; pol++)
      for (int i = 0; i < n; i += jump)
        v[l % 2][pol + i] = v[(l + 1) % 2][pol + (2 * i) % n] +
                            v[(l + 1) % 2][pol + (2 * i + jump) % n] * prep[i];
  return vector<point>(v[k % 2], v[k % 2] + n);
}
vector<point> to_points(vector<int> *v) {
  vector<point> res(v->size());
  for (int i = 0; i < v->size(); i++) res[i] = point(v->at(i), 0);
  return res;
}
void cut(vector<int> *res) {
  while (!res->back()) res->pop_back();
}
vector<int> *brute(vector<int> *a, vector<int> *b) {
  vector<int> *res = new vector<int>(a->size() + b->size());
  for (int i = 0; i < a->size(); i++)
    for (int j = 0; j < b->size(); j++)
      res->at(i + j) = (res->at(i + j) + a->at(i) * b->at(j)) % 1009;
  cut(res);
  return res;
}
vector<int> *multiply(vector<int> *a, vector<int> *b) {
  if (a->size() * b->size() < 10000) return brute(a, b);
  vector<point> A, B;
  A = to_points(a);
  B = to_points(b);
  delete a;
  delete b;
  int n = 2;
  while (n < A.size() || n < B.size()) n *= 2;
  n *= 2;
  A.resize(n, 0);
  B.resize(n, 0);
  A = dft(A, 1);
  B = dft(B, 1);
  vector<point> V(n);
  for (int i = 0; i < n; i++) V[i] = A[i] * B[i];
  V = dft(V, -1);
  vector<int> *res = new vector<int>(n);
  for (int i = 0; i < n; i++)
    res->at(i) = (long long)(round(real(V[i]) / n)) % 1009LL;
  cut(res);
  return res;
}
int n, m, k;
int cnt[200007];
vector<vector<int> *> V, V2;
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    cnt[x]++;
  }
  for (int i = 1; i <= m; i++) {
    if (cnt[i]) {
      V.push_back(new vector<int>(cnt[i] + 1, 1));
    }
  }
  while (V.size() > 1) {
    for (int i = 0; i < V.size(); i += 2) {
      if (i + 1 < V.size())
        V2.push_back(multiply(V[i], V[i + 1]));
      else
        V2.push_back(V[i]);
    }
    V.clear();
    swap(V, V2);
  }
  printf("%d\n", V[0]->at(k));
  return 0;
}
