#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int MOD = 1009;
namespace FFT {
const double PI = acosl(-1);
int GetID(int i, int n) {
  n >>= 1;
  int res = 0;
  while (i) {
    if (i & 1) {
      res += n;
    }
    i >>= 1;
    n >>= 1;
  }
  return res;
}
void FFT(vector<complex<double> >& v, bool inverse) {
  int N = (int)v.size();
  for (int i = 0; i < N; ++i) {
    int x = GetID(i, N);
    if (i < x) {
      swap(v[i], v[x]);
    }
  }
  for (int len = 2; len <= N; len <<= 1) {
    double angle = 2.0 * PI / len;
    if (inverse) angle *= -1;
    complex<double> temp(cosl(angle), sinl(angle));
    for (int i = 0; i < N; i += len) {
      complex<double> x = 1;
      for (int j = i; j < i + len / 2; ++j) {
        complex<double> t1 = v[j], t2 = x * v[j + len / 2];
        v[j] = t1 + t2;
        v[j + len / 2] = t1 - t2;
        x *= temp;
      }
    }
  }
  if (inverse) {
    for (auto& x : v) x /= N;
  }
}
vector<long long> MultPoly(vector<long long>& P1, vector<long long>& P2) {
  int N = 1;
  while (N < ((int)P1.size() + (int)P2.size())) N <<= 1;
  vector<complex<double> > a(N), b(N);
  for (int i = 0; i < (int)P1.size(); ++i) a[i] = P1[i];
  for (int i = 0; i < (int)P2.size(); ++i) b[i] = P2[i];
  FFT(a, 0);
  FFT(b, 0);
  for (int i = 0; i < N; ++i) {
    a[i] *= b[i];
  }
  FFT(a, 1);
  vector<long long> res(N);
  for (int i = 0; i < N; ++i) res[i] = (long long)round(a[i].real()) % 1009ll;
  while (res.back() == 0) res.pop_back();
  return res;
}
}  // namespace FFT
int main() {
  int n, m, k;
  cin >> n >> m >> k;
  map<int, int> colors;
  for (int i = 0; i < n; ++i) {
    int c;
    cin >> c;
    colors[c]++;
  }
  vector<vector<long long> > polys((int)colors.size());
  int id = 0;
  for (auto& x : colors) {
    polys[id].resize(x.second + 1, 1);
    ++id;
  }
  for (int len = 2; len <= 2 * (int)polys.size(); len <<= 1) {
    for (int j = 0; j < (int)polys.size(); j += len) {
      if (j + len / 2 < (int)polys.size()) {
        polys[j] = FFT::MultPoly(polys[j], polys[j + len / 2]);
      }
    }
  }
  if (k >= (int)polys[0].size())
    cout << 0;
  else
    cout << polys[0][k] << "\n";
  return 0;
}
