#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;
const double PI = acos(-1.0L);
void fft(vector<cd> &a, int invert = 0) {
  int n = 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 angle = 2.0 * PI / len * (invert ? -1 : 1);
    cd w(cos(angle), sin(angle));
    for (int i = 0; i < n; i += len) {
      cd cur(1.0);
      for (int j = 0; (j << 1) < len; j++) {
        cd u = a[i + j], v = a[i + j + len / 2] * cur;
        a[i + j] = u + v;
        a[i + j + len / 2] = u - v;
        cur *= w;
      }
    }
  }
  if (invert)
    for (cd &e : a) e /= n;
}
void multiply(vector<cd> &a, vector<cd> &b) {
  int n = a.size() + b.size() - 1;
  int log_n = 0;
  while (n > (1 << log_n)) log_n++;
  n = 1 << log_n;
  a.resize(n);
  b.resize(n);
  fft(a);
  fft(b);
  for (int i = 0; i < n; i++) a[i] *= b[i];
  fft(a, 1);
  for (int i = 0; i < n; i++)
    a[i] = ((long long)round(a[i].real() + 1e-6)) % 1009ll;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<cd> *util = new vector<cd>[m];
  for (int i = 0; i < m; i++) util[i].push_back(1.0);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x--;
    util[x].push_back(1.0);
  }
  priority_queue<pair<int, int> > Q;
  for (int i = 0; i < m; i++) Q.push(pair<int, int>(-util[i].size(), i));
  while (Q.size() > 1) {
    pair<int, int> u = Q.top();
    Q.pop();
    pair<int, int> v = Q.top();
    Q.pop();
    multiply(util[u.second], util[v.second]);
    Q.push(pair<int, int>(-util[u.second].size(), u.second));
    util[v.second].clear();
  }
  int fin = Q.top().second;
  cout << util[fin][k].real() << endl;
  return 0;
}
