#include <bits/stdc++.h>
using namespace std;
struct Complex {
  double x, y;
  Complex(double a = 0, double b = 0) : x(a), y(b) {}
  Complex operator+(Complex r) { return Complex(x + r.x, y + r.y); }
  Complex operator-(Complex r) { return Complex(x - r.x, y - r.y); }
  Complex operator*(Complex r) {
    return Complex(x * r.x - y * r.y, x * r.y + y * r.x);
  }
  Complex operator/(double d) { return Complex(x / d, y / d); }
};
const double PI = acos(-1);
const int M = 1009;
struct FFT {
  int N;
  vector<int> perm;
  void precalculate() {
    perm.resize(N);
    perm[0] = 0;
    for (int k = 1; k < N; k <<= 1) {
      for (int i = 0; i < k; i++) {
        perm[i] <<= 1;
        perm[i + k] = 1 + perm[i];
      }
    }
  }
  void fft(vector<Complex> &v, bool invert = false) {
    if (v.size() != perm.size()) {
      N = v.size();
      assert(N && (N & (N - 1)) == 0);
      precalculate();
    }
    for (int i = 0; i < N; i++)
      if (i < perm[i]) swap(v[i], v[perm[i]]);
    for (int len = 2; len <= N; len <<= 1) {
      double angle = 2 * PI / len;
      if (invert) angle = -angle;
      Complex factor(cos(angle), sin(angle));
      for (int i = 0; i < N; i += len) {
        Complex w(1);
        for (int j = 0; j < len / 2; j++) {
          Complex x = v[i + j], y = w * v[i + j + len / 2];
          v[i + j] = x + y;
          v[i + j + len / 2] = x - y;
          w = w * factor;
        }
      }
    }
    if (invert)
      for (Complex &x : v) x = x / N;
  }
  vector<int> multiply(const vector<int> &a, const vector<int> &b) {
    vector<Complex> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n);
    fb.resize(n);
    fft(fa);
    fft(fb);
    for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i];
    fft(fa, true);
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
      long long cur = round(fa[i].x);
      ans[i] = cur % M;
    }
    return ans;
  }
  vector<int> multiply2(const vector<int> &a, const vector<int> &b) {
    vector<int> ans(a.size() + b.size());
    for (int i = 0; i < a.size(); i++)
      for (int j = 0; j < b.size(); j++)
        ans[i + j] = (ans[i + j] + a[i] * b[j]) % M;
    return ans;
  }
};
FFT fft;
const int K = 3000;
vector<int> multiply(const vector<int> &cnt, int l, int r) {
  if (l == r) {
    return vector<int>(cnt[l] + 1, 1);
  }
  int mid = (l + r) / 2;
  vector<int> left = multiply(cnt, l, mid);
  vector<int> right = multiply(cnt, mid + 1, r);
  vector<int> ans;
  if (left.size() < K && right.size() < K)
    ans = fft.multiply2(left, right);
  else
    ans = fft.multiply(left, right);
  while (ans.back() == 0) ans.pop_back();
  return ans;
}
int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> cnt(m);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x--;
    cnt[x]++;
  }
  vector<int> ans = multiply(cnt, 0, m - 1);
  cout << ans[k] << endl;
}
