#include <bits/stdc++.h>
using namespace std;
const long long N = 1e6 + 7;
const double PI = acos(-1);
long long mod = 998244353;
vector<long long> res(N, 0);
void fft(vector<complex<double> > &a, long long n, bool invert) {
  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 && j < n) {
      complex<double> tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }
  }
  for (int len = 2; len <= n; len <<= 1) {
    double ang = (2 * PI / len) * (invert ? -1 : 1);
    complex<double> wlen(cos(ang), sin(ang));
    for (int i = 0; i < n; i += len) {
      complex<double> w(1);
      for (int j = 0; j < len / 2; j++) {
        complex<double> 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;
  }
}
vector<complex<double> > p1(N, 0), p2(N, 0);
void multiply(vector<long long> &f1, long long sz1, vector<long long> &f2,
              long long sz2, vector<long long> &res) {
  long long n = 1;
  for (int i = 0; i < sz1; i++) p1[i] = f1[i];
  for (int i = 0; i < sz2; i++) p2[i] = f2[i];
  while (n < sz1 + sz2) n <<= 1;
  for (int i = sz1; i < n; i++) p1[i] = 0;
  for (int i = sz2; i < n; i++) p2[i] = 0;
  fft(p1, n, false);
  fft(p2, n, false);
  for (int i = 0; i < n; i++) p1[i] *= p2[i];
  fft(p1, n, true);
  int deg = sz1 - 1 + sz2;
  for (int i = 0; i < deg; i++) res[i] = (long long)round(p1[i].real()) % mod;
  for (int i = deg; i < n; i++) res[i] = 0;
}
vector<long long> input, r1(N, 0), r2(N, 0), t1(N, 0), r11(N, 0), r22(N, 0);
void dnc(long long l, long long r, long long sz, vector<long long> &res) {
  if (r == l) {
    for (int i = 0; i <= sz; i++) res[i] = 1;
    return;
  }
  long long sum = 0;
  long long i = l;
  for (i = l; i <= r; i++) {
    sum += input[i];
    if (sum > sz / 2) break;
  }
  long long idx = max(i - 1, l);
  sum -= input[i];
  vector<long long> tmp;
  dnc(l, max(i - 1, l), sum, r1);
  for (int i = 0; i <= sum; i++) tmp.push_back(r1[i]);
  dnc(max(i - 1, l) + 1, r, sz - sum, r2);
  for (int i = 0; i <= sum; i++) r1[i] = tmp[i];
  multiply(r1, sum + 1, r2, sz - sum + 1, t1);
  for (int i = 0; i <= sz; i++) {
    res[i] = t1[i];
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, m, k, a;
  vector<long long> v;
  map<long long, long long> mp, ff;
  cin >> n >> m >> k;
  mod = 1009;
  for (int i = 0; i < n; i++) {
    cin >> a;
    mp[a]++;
  }
  long long sum = 0;
  for (auto it : mp) {
    if (it.second == 0) continue;
    input.push_back(it.second);
    sum += it.second;
  }
  sort(input.begin(), input.end());
  dnc(0, input.size() - 1, sum, res);
  cout << res[k] % mod << "\n";
  multiply(t1, 4, res, 3, res);
  return 0;
}
