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;
namespace math {
inline uint32_t nextPow2_32(uint32_t v) {
  if (!v) {
    return 1;
  }
  uint32_t res = 1U << (31 - __builtin_clz(v));
  return res == v ? res : res << 1;
}
template <typename T = double>
struct Complex {
  inline Complex(T _real = 0, T _imag = 0) : real(_real), imag(_imag) {}
  inline void operator=(const Complex<T>& o) {
    real = o.real;
    imag = o.imag;
  }
  inline void operator+=(const Complex<T>& o) {
    real += o.real;
    imag += o.imag;
  }
  inline Complex<T> operator-(const Complex<T>& o) const {
    Complex<T> res;
    res.initSub(*this, o);
    return res;
  }
  inline Complex<T> operator*(const Complex<T>& o) const {
    Complex<T> res;
    res.initMul(*this, o);
    return res;
  }
  inline void operator/=(T scale) {
    real /= scale;
    imag /= scale;
  }
  inline void init(T _real = 0, T _imag = 0) {
    real = _real;
    imag = _imag;
  }
  inline void initConj(const Complex<T>& o) {
    real = o.real;
    imag = -o.imag;
  }
  inline void initPolar(T r, T theta) {
    real = r * cos(theta);
    imag = r * sin(theta);
  }
  inline void initMul(const Complex<T>& x, const Complex<T>& y) {
    real = x.real * y.real - x.imag * y.imag;
    imag = x.real * y.imag + x.imag * y.real;
  }
  inline void initSub(const Complex<T>& x, const Complex<T>& y) {
    real = x.real - y.real;
    imag = x.imag - y.imag;
  }
  inline Complex<T> conj() const { return Complex<T>(real, -imag); }
  inline void flip() {
    real = -real;
    imag = -imag;
  }
  T real, imag;
};
const long double PI = acos(static_cast<long double>(-1));
template <typename T = double>
struct FFTUtils {
  inline FFTUtils(int capacity = -1) {
    if (capacity > 0) {
      capacity = nextPow2_32(capacity);
    }
    capacity = max(capacity, 4);
    _revs.reserve(capacity);
    _revs.resize(2);
    _revs[0] = 0;
    _revs[1] = 1;
    _roots.reserve(capacity | 1);
    _roots.resize(3);
    _roots[0].init(0, 0);
    _roots[1].init(1, 0);
    _roots[2].init(1, 0);
    _initCapacity(capacity);
    _cs.reserve(capacity);
  }
  inline const vector<Complex<T>>& mul(const vector<int>& x,
                                       const vector<int>& y, int n = -1) {
    int xy = max(static_cast<int>(x.size() + y.size()) - 1, 4);
    if (n < 0) {
      n = xy;
    } else {
      n = max(min(n, xy), 4);
    }
    int pow2 = nextPow2_32(n);
    _cs.resize(pow2);
    for (size_t i = 0; i < pow2; ++i) {
      _cs[i].init(i < x.size() ? x[i] : 0, i < y.size() ? y[i] : 0);
    }
    fft(_cs, false, pow2);
    _c.init(0, -0.25);
    for (int i = 0; i <= (pow2 >> 1); ++i) {
      int j = (pow2 - i) & (pow2 - 1);
      _c2.initMul(_cs[i] * _cs[i] - (_cs[j] * _cs[j]).conj(), _c);
      _cs[i].initConj(_c2);
      _cs[j] = _c2;
    }
    fft(_cs, false, pow2);
    for (auto& c : _cs) {
      c /= pow2;
    }
    _shrink(_cs);
    return _cs;
  }
  inline void fft(vector<Complex<T>>& cs, bool invert, int n = -1) {
    int pow2 = max(nextPow2_32(n < 0 ? static_cast<int>(cs.size()) : n), 4U);
    _initCapacity(pow2);
    _expand(pow2, cs);
    int shift = __builtin_ctz(_revs.size()) - __builtin_ctz(pow2);
    for (int i = 0; i < pow2; ++i) {
      int j = _revs[i] >> shift;
      if (i < j) {
        swap(cs[i], cs[j]);
      }
    }
    for (int l = 1; l < pow2; l <<= 1) {
      for (int i = 0, l2 = l << 1; i < pow2; i += l2) {
        int step = invert ? -1 : 1;
        for (int j = 0, k = invert ? (l << 1) : l; j < l; ++j, k += step) {
          _c.initMul(cs[i + j + l], _roots[k]);
          if (invert && j) {
            _c.flip();
          }
          cs[i + j + l].initSub(cs[i + j], _c);
          cs[i + j] += _c;
        }
      }
    }
    if (invert) {
      for (int i = 0; i < pow2; ++i) {
        cs[i] /= pow2;
      }
    }
  }
  inline void _expand(int pow2, vector<Complex<T>>& cs) {
    for (size_t i = cs.size(); i < pow2; ++i) {
      cs.emplace_back(0, 0);
    }
  }
  inline void _shrink(vector<Complex<T>>& cs) {
    for (; cs.size() > 1 && cs.back().real < 0.5; cs.pop_back()) {
    }
  }
  inline void _initCapacity(int pow2) {
    if (_revs.size() >= pow2) {
      return;
    }
    int oldPow2 = _revs.size(), lgN = __builtin_ctz(pow2);
    _revs.resize(pow2);
    for (int i = 0; i < pow2; ++i) {
      _revs[i] = (_revs[i >> 1] >> 1) + ((i & 1) << (lgN - 1));
    }
    _roots.resize(pow2 | 1);
    for (int i = oldPow2; i < pow2; i <<= 1) {
      T angle = PI / i, baseAngle = angle * 2;
      for (int j = i; j < i << 1; j += 2, angle += baseAngle) {
        _roots[j] = _roots[j >> 1];
        _roots[j | 1].initPolar(1, angle);
      }
    }
    _roots[pow2] = _roots[pow2 >> 1];
  }
  vector<int> _revs;
  vector<Complex<T>> _roots, _cs;
  Complex<T> _c;
  Complex<T> _c2;
};
}  // namespace math
const int MAXN = 200000 + 2;
const int MAXN_05 = sqrt(MAXN) + 1;
const int MOD = 1009;
using COMPLEX_T = long double;
int n, m, k, k1;
int colorCnt[MAXN], cntCnt[MAXN];
vector<vector<int>> vs;
math::FFTUtils<COMPLEX_T> fft;
inline void assign(vector<int>& res,
                   const vector<math::Complex<COMPLEX_T>>& cs) {
  res.resize(cs.size());
  for (size_t i = 0; i < cs.size(); ++i) {
    res[i] = static_cast<int64_t>(cs[i].real + 0.5) % MOD;
  }
}
inline vector<int> calcExp(int n, int e) {
  if (e == 1) {
    vector<int> res;
    res.resize(n + 1);
    fill(res.begin(), res.end(), 1);
    return res;
  }
  vector<int> res;
  res.resize(1);
  res[0] = 1;
  vector<int> base;
  base.resize(n + 1);
  fill(base.begin(), base.end(), 1);
  for (; e; e >>= 1) {
    if (e & 1) {
      assign(res, fft.mul(res, base, k1));
    }
    assign(base, fft.mul(base, base, k1));
  }
  return res;
}
inline void mulInline(vector<int>& xs, const vector<int>& ys) {
  assign(xs, fft.mul(xs, ys, k1));
}
int main() {
  vs.reserve(MAXN_05);
  scanf("%d%d%d", &n, &m, &k);
  k1 = k + 1;
  for (int i = 0; i < n; ++i) {
    int c;
    scanf("%d", &c);
    ++colorCnt[c - 1];
  }
  for (int i = 0; i < m; ++i) {
    if (colorCnt[i] > 0) {
      ++cntCnt[colorCnt[i]];
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (cntCnt[i]) {
      vs.push_back(calcExp(i, cntCnt[i]));
    }
  }
  while (vs.size() > 1) {
    sort(vs.begin(), vs.end(), [](const vector<int>& x, const vector<int>& y) {
      return x.size() < y.size();
    });
    for (int i = 0, j = static_cast<int>(vs.size()) - 1; i < j; ++i, --j) {
      assign(vs[i], fft.mul(vs[i], vs[j], k1));
    }
    vs.erase(vs.begin() + ((vs.size() + 1) >> 1), vs.end());
  }
  printf("%d\n", vs.back()[k]);
}
