10 2 5
1 1 1 2 2 2 2 2 2 2
 10 2 5
1 1 1 1 1 1 2 2 2 2
 3 3 2
1 3 1
 8 8 7
7 2 8 6 8 5 3 8
 7 7 5
2 6 3 6 3 5 1
 5 5 1
5 2 5 1 2
 6 6 6
5 6 5 3 4 2
 5 5 2
2 3 2 2 4
 3 3 3
1 1 1
 111 78 54
24 13 49 22 52 38 38 63 21 10 9 56 60 47 11 78 23 52 55 12 72 33 17 14 33 59 21 32 20 73 1 60 27 64 23 74 36 49 69 14 29 37 19 61 52 33 26 27 10 11 34 25 62 47 36 12 63 45 31 71 78 1 6 26 36 65 56 46 19 28 77 64 56 8 77 38 3 33 63 77 40 7 22 13 60 14 57 43 51 10 30 21 7 67 32 11 12 9 72 24 27 67 25 63 6 67 69 37 26 19 26
 10 2 5
1 1 1 1 1 1 1 1 1 2
 6 6 1
4 5 6 3 5 3
 10 2 5
1 1 1 1 2 2 2 2 2 2
 8 8 3
8 8 2 7 8 2 3 5
 7 7 4
4 6 6 7 2 5 3
 10 2 5
2 2 2 2 2 2 2 2 2 2
 111 67 97
32 67 4 15 17 17 23 6 39 54 19 62 28 59 63 36 44 40 28 67 28 3 55 19 11 26 3 38 22 26 62 54 61 15 22 4 47 53 27 36 31 5 16 59 51 62 51 46 7 55 26 66 50 51 32 17 54 14 18 14 40 30 24 2 61 16 16 27 55 58 35 7 26 3 26 4 13 59 14 32 56 54 5 46 39 30 45 24 37 12 67 38 45 32 41 21 46 26 41 29 15 28 65 5 19 53 13 31 58 18 57
 6 6 2
4 4 2 4 2 3
 10 2 5
1 1 1 1 1 2 2 2 2 2
 10 2 5
1 1 1 1 1 1 1 1 2 2
 6 6 4
5 2 4 3 1 5
 10 2 5
1 1 2 2 2 2 2 2 2 2
 1 1 1
1
 8 8 5
7 5 6 8 2 8 3 4
 10 2 5
1 1 1 1 1 1 1 2 2 2
 111 101 52
54 69 33 81 8 90 48 21 96 35 44 75 68 34 101 82 93 94 86 76 33 91 5 70 22 84 70 71 62 81 50 83 51 43 95 46 19 53 101 34 51 40 6 17 69 60 73 89 65 75 59 68 62 49 89 23 63 83 86 68 62 39 1 18 3 75 44 57 9 24 67 81 83 45 93 66 79 71 43 49 17 2 33 38 98 71 71 21 56 16 31 2 75 61 64 38 69 80 81 12 68 95 26 9 69 82 41 35 75 7 71
 3 3 3
3 3 1
 4 4 2
2 4 4 3
 10 2 5
1 2 2 2 2 2 2 2 2 2
 4 4 4
4 4 4 4
 3 3 2
1 2 3
 2 1 2
1 1
 5 5 3
3 4 1 5 5
 7 7 1
2 6 5 6 2 3 3
 111 9 57
9 9 2 6 8 6 5 8 9 7 3 9 1 2 6 6 5 3 1 1 6 1 8 4 3 9 8 6 8 1 9 8 5 8 6 9 4 5 7 3 1 6 4 3 2 5 7 3 1 7 9 1 7 1 3 5 9 5 6 2 2 7 9 7 1 5 5 5 5 2 6 5 7 3 8 9 7 3 6 5 1 9 2 9 9 8 8 7 9 1 6 2 4 5 7 4 8 9 9 2 7 7 6 9 8 2 1 3 3 1 5
 4 4 1
2 4 1 4
 2 1 1
1 1
 111 16 58
15 6 4 7 7 10 16 2 3 1 4 8 10 1 2 11 6 6 14 16 6 16 1 2 13 2 7 13 1 4 1 4 12 2 4 11 15 12 9 13 10 4 11 7 5 3 12 11 11 3 16 15 9 6 15 11 4 14 8 15 16 3 9 10 9 1 8 4 14 7 13 5 1 8 5 11 8 14 1 8 15 2 5 2 4 5 9 2 10 11 11 5 7 11 11 14 5 16 14 2 4 11 12 10 7 14 2 5 3 2 1
 2 2 2
1 1

4
 5
 2
 6
 12
 3
 1
 4
 1
 648
 2
 4
 5
 19
 25
 1
 214
 5
 6
 3
 11
 3
 1
 41
 4
 881
 1
 4
 2
 1
 3
 1
 7
 4
 446
 3
 1
 552
 1

#include <bits/stdc++.h>
using namespace std;
template <typename dbl>
struct cplx {
  dbl x, y;
  cplx(dbl x_ = 0, dbl y_ = 0) : x(x_), y(y_) {}
  friend cplx operator+(cplx a, cplx b) { return cplx(a.x + b.x, a.y + b.y); }
  friend cplx operator-(cplx a, cplx b) { return cplx(a.x - b.x, a.y - b.y); }
  friend cplx operator*(cplx a, cplx b) {
    return cplx(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
  }
  friend cplx conj(cplx a) { return cplx(a.x, -a.y); }
  friend cplx inv(cplx a) {
    dbl n = (a.x * a.x + a.y * a.y);
    return cplx(a.x / n, -a.y / n);
  }
};
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* ch) { return string(ch); }
string to_string(char ch) { return (string) "'" + ch + (string) "'"; }
string to_string(bool b) { return (b ? "true" : "false"); }
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
string to_string(complex<double> a) {
  return "(" + to_string(real(a)) + ", " + to_string(imag(a)) + ")";
}
string to_string(vector<complex<double>> a) {
  string res = "{";
  bool first = true;
  int n = a.size();
  for (int i = 0; i < n; i++) {
    auto x = a[i];
    if (first == false) res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
string to_string(cplx<double> a) {
  return "(" + to_string((a.x)) + ", " + to_string((a.y)) + ")";
}
string to_string(vector<cplx<double>> a) {
  string res = "{";
  bool first = true;
  int n = a.size();
  for (int i = 0; i < n; i++) {
    auto x = a[i];
    if (first == false) res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A>
string to_string(A a) {
  string res = "{";
  bool first = true;
  for (const auto& x : a) {
    if (first == false) res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug() { cerr << "]\n"; }
template <class H, class... T>
void debug(H head, T... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}
using cd = cplx<double>;
const double PI = acos(-1);
class FFT {
 public:
  static int base;
  static vector<int> rev;
  static vector<cd> roots;
  static void init() {
    rev = {0, 1};
    roots = vector<cd>(2, 1);
    base = 1;
  }
  static void ensure_base(int new_base) {
    if (roots.empty() || rev.empty()) {
      init();
    }
    if (base >= new_base) {
      return;
    }
    rev.resize(1 << new_base);
    for (int i = 0; i < (1 << new_base); i++) {
      rev[i] = ((rev[i / 2] >> 1) | (i % 2) << (new_base - 1));
    }
    roots.resize(1 << new_base);
    while (base < new_base) {
      const auto z1 = polar(1.0, PI / (1 << base));
      const auto z = cd(real(z1), imag(z1));
      for (int i = (1 << (base - 1)); i < (1 << base); i++) {
        roots[i << 1] = roots[i];
        roots[(i << 1) + 1] = roots[i] * z;
      }
      base++;
    }
  }
  static void fft(vector<cd>& a) {
    int n = a.size();
    int zeros = __builtin_ctz(n);
    ensure_base(zeros);
    int shift = base - zeros;
    for (int i = 0; i < n; i++) {
      if (i < (rev[i] >> shift)) swap(a[i], a[rev[i] >> shift]);
    }
    for (int k = 1; k < n; k *= 2) {
      for (int i = 0; i < n; i += 2 * k) {
        for (int j = 0; j < k; j++) {
          auto x = a[i + j], y = a[i + j + k] * roots[k + j];
          a[i + j] = x + y;
          a[i + j + k] = x - y;
        }
      }
    }
  }
  template <typename T>
  static vector<T> multiply(vector<T> a, vector<T> b) {
    if (a.empty() || b.empty()) return {};
    int total = int(a.size() + b.size()) - 1;
    int n = 1 << (32 - __builtin_clz(total));
    ;
    vector<cd> A(n), B(n);
    for (int i = 0; i < n; i++) {
      T x = (i < int(a.size()) ? a[i] : 0);
      T y = (i < int(b.size()) ? b[i] : 0);
      A[i] = cd(x, y);
    }
    fft(A);
    for (auto& i : A) {
      i = i * i;
    }
    for (int i = 0; i < n; i++) {
      B[i] = A[(n - i) & (n - 1)] - conj(A[i]);
    }
    fft(B);
    ;
    vector<T> res(total);
    for (int i = 0; i < total; i++) {
      res[i] = (llround(B[i].y)) / (4 * n);
    }
    return res;
  }
  template <typename T, typename Z = int64_t>
  static vector<T> multiply_mod(vector<T> a, vector<T> b, Z m) {
    if (a.empty() || b.empty()) return {};
    int total = int(a.size() + b.size()) - 1;
    int n = 1 << (32 - __builtin_clz(total));
    vector<cd> A(n), B(n);
    const int shift = 15;
    for (int i = 0; i < int(a.size()); i++) {
      T x = (a[i] % m + m) % m;
      A[i] = cd(x & ((1 << shift) - 1), x >> shift);
    }
    fft(A);
    if (a == b)
      B = A;
    else {
      for (int i = 0; i < int(b.size()); i++) {
        T x = (b[i] % m + m) % m;
        B[i] = cd(x & ((1 << shift) - 1), x >> shift);
      }
      fft(B);
    }
    double ratio = 0.25 / n;
    cd r2(0, -1);
    cd r3(ratio, 0);
    cd r4(0, -ratio);
    cd r5(0, 1);
    for (int i = 0; i <= (n >> 1); i++) {
      int j = (n - i) & (n - 1);
      cd a1 = (A[i] + conj(A[j]));
      cd a2 = (A[i] - conj(A[j])) * r2;
      cd b1 = (B[i] + conj(B[j])) * r3;
      cd b2 = (B[i] - conj(B[j])) * r4;
      if (i != j) {
        cd c1 = (A[j] + conj(A[i]));
        cd c2 = (A[j] - conj(A[i])) * r2;
        cd d1 = (B[j] + conj(B[i])) * r3;
        cd d2 = (B[j] - conj(B[i])) * r4;
        A[i] = c1 * d1 + c2 * d2 * r5;
        B[i] = c1 * d2 + c2 * d1;
      }
      A[j] = a1 * b1 + a2 * b2 * r5;
      B[j] = a1 * b2 + a2 * b1;
    }
    fft(A);
    fft(B);
    vector<T> res(total);
    for (int i = 0; i < total; i++) {
      Z aa = llround(A[i].x);
      Z bb = llround(B[i].x);
      Z cc = llround(A[i].y);
      res[i] = static_cast<T>((aa + ((bb % m) << 15) + ((cc % m) << 30)) % m);
    }
    return res;
  }
};
int FFT::base;
vector<int> FFT::rev;
vector<cd> FFT::roots;
template <typename T>
vector<T> operator*(const vector<T>& A, const vector<T>& B) {
  if (min((int)A.size(), (int)B.size()) < 0) {
    vector<T> C((int)A.size() + (int)B.size() - 1);
    for (int i = 0; i < (int)A.size(); i++) {
      for (int j = 0; j < (int)B.size(); j++) {
        C[i + j] += A[i] * B[j];
      }
    }
    return C;
  }
  return FFT::multiply<T>(A, B);
}
template <typename T>
vector<T> operator*=(vector<T>& A, const vector<T>& B) {
  return A = A * B;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    mp[x]++;
  }
  vector<pair<int, int>> a;
  for (auto& i : mp) {
    a.push_back(make_pair(i.second, i.first));
  }
  sort(a.begin(), a.end());
  vector<int64_t> ans(a.front().first + 1, 1);
  for (int i = 1; i < int(a.size()); i++) {
    vector<int64_t> cur(a[i].first + 1, 1);
    ans *= cur;
  }
  cout << ans[k] % 1009 << '\n';
  return 0;
}
