#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 18;
const int mod = 1009;
const double PI = acos(-1.0);
int n, m, k, tot[N];
struct Complex {
  double x, y;
  Complex(double x = 0.0, double y = 0.0) : x(x), y(y) {}
  Complex operator+(const Complex &b) const {
    return Complex(x + b.x, y + b.y);
  }
  Complex operator-(const Complex &b) const {
    return Complex(x - b.x, y - b.y);
  }
  Complex operator*(const Complex &b) const {
    return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
  }
} w[N];
vector<int> c[N << 1];
int cnt = 0;
struct cmp {
  bool operator()(int a, int b) { return c[a].size() > c[b].size(); }
};
priority_queue<int, vector<int>, cmp> heap;
Complex x1[N << 1], x2[N << 1];
void change(Complex y[], int len) {
  for (int i = 1, j = len / 2; i < len - 1; i++) {
    if (i < j) swap(y[i], y[j]);
    int k = len / 2;
    while (j >= k) {
      j -= k;
      k /= 2;
    }
    if (j < k) j += k;
  }
}
void fft(Complex y[], int len, int on) {
  change(y, len);
  for (int h = 2; h <= len; h <<= 1) {
    Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h));
    for (int j = 0; j < len; j += h) {
      Complex w(1, 0);
      for (int k = j; k < j + h / 2; k++) {
        Complex u = y[k];
        Complex t = w * y[k + h / 2];
        y[k] = u + t;
        y[k + h / 2] = u - t;
        w = w * wn;
      }
    }
  }
  if (on == -1) {
    for (int i(0); i <= (len - 1); ++i) y[i].x /= len;
  }
}
void mul(vector<int> &a, vector<int> &b, vector<int> &c) {
  int len = 1;
  int sz1 = a.size(), sz2 = b.size();
  while (len <= sz1 + sz2 - 1) len <<= 1;
  for (int i(0); i <= (sz1 - 1); ++i) x1[i] = Complex(a[i], 0);
  for (int i(sz1); i <= (len); ++i) x1[i] = Complex(0, 0);
  for (int i(0); i <= (sz2 - 1); ++i) x2[i] = Complex(b[i], 0);
  for (int i(sz2); i <= (len); ++i) x2[i] = Complex(0, 0);
  fft(x1, len, 1);
  fft(x2, len, 1);
  for (int i(0); i <= (len - 1); ++i) x1[i] = x1[i] * x2[i];
  fft(x1, len, -1);
  c.clear();
  for (int i(0); i <= (sz1 + sz2 - 2); ++i) {
    c.push_back((long long)(x1[i].x + 0.5) % mod);
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i(1); i <= (n); ++i) {
    int x;
    scanf("%d", &x);
    tot[x]++;
  }
  for (int i(1); i <= (m); ++i) {
    if (tot[i] == 0) continue;
    c[++cnt].clear();
    for (int j(0); j <= (tot[i]); ++j) c[cnt].push_back(1);
    heap.push(cnt);
  }
  while (heap.size() >= 2) {
    int x = heap.top();
    heap.pop();
    int y = heap.top();
    heap.pop();
    mul(c[x], c[y], c[++cnt]);
    c[x].clear(), c[y].clear();
    heap.push(cnt);
  }
  printf("%d", c[cnt][k]);
  return 0;
}
