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

//#pragma comment(linker, "/STACK:268435456")
//#pragma comment(linker, "/HEAP:1000000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

const uint64_t FIXED_SEED = 123;

const auto START_TIME = chrono::steady_clock::now();
const uint64_t RANDOM_SEED = START_TIME.time_since_epoch().count();
const uint64_t XORSHIFT_SEED = FIXED_SEED;

#include <bits/extc++.h>

template<class T> class custom_hash;

template<class K, class V> using __hash_table = __gnu_pbds::gp_hash_table<
    K, V, custom_hash<K>, equal_to<K>, __gnu_pbds::direct_mask_range_hashing<K>, __gnu_pbds::linear_probe_fn<>,
    __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<>, __gnu_pbds::hash_load_check_resize_trigger<true>, true>
>;

template<class K, class V = __gnu_pbds::null_type> class hash_table : public __hash_table<K, V> {
public:
    hash_table() : __hash_table<K, V>() {
        this->set_loads({.25, .5});  // Sets the loads through a pair of the minimal and maximal loads, respectively.
    }
    template<class It> hash_table(It b, It e) : hash_table() {
        this->resize(distance(b, e));
        for (; b != e; this->insert(*b++));
    }
    size_t count(const K& k) {
        return this->find(k) != this->end();
    }
};

template<class K, class V = __gnu_pbds::null_type> using ordered_set = __gnu_pbds::tree<
    K,
    V,
    less<K>,
    __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update
>;  // find_by_order, order_of_key

#define all(a) a.begin(), a.end()
#define X first
#define Y second
#ifndef LOCAL
    #define cerr if(0)cerr
#endif

template<class T> istream& operator>>(istream& is, vector<T>& v) {
    for (T& it : v) is >> it;
    return is;
}

template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p);

template<class C, enable_if_t<!is_void<decltype(declval<C>().begin())>::value && !is_same<C, string>::value, int> = 0>
ostream& operator<<(ostream& os, const C& c) {
#ifdef LOCAL
    os << "[";
    auto it = c.begin(), e = c.end();
    if (it != e) {
        for (os << *it; ++it != e; os << ", " << *it);
    }
    os << "]";
#else
    for (const auto& it : c) os << *it << ' ';
#endif
    return os;
}

template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template<class T, enable_if_t<is_same<T, __int128_t>::value || is_same<T, __uint128_t>::value, int> = 0>
istream& operator>>(istream& is, T& x) {
    static char s[41];
    is >> s;
    x = 0;
    if (s[0] == '-') for (int i = 0; s[++i] != '\0'; x = 10 * x - (s[i] - '0'));
    else for (int i = -1; s[++i] != '\0'; x = 10 * x + (s[i] - '0'));
    return is;
}

template<class T, enable_if_t<is_same<T, __int128_t>::value || is_same<T, __uint128_t>::value, int> = 0>
ostream& operator<<(ostream& os, T x) {
    if (!x) return os << '0';
    static char s[41];
    bool sign = x < 0;
    if (sign) x = -x;
    int i = 0;
    for (; x; s[i++] = '0' + x % 10, x /= 10);
    if (sign) s[i++] = '-';
    reverse(s, s + i);
    s[i] = '\0';
    return os << s;
}

size_t CombineHashes(size_t l, size_t r) {
    return l ^ ( r + 0x9e3779b9 + (l << 6) + (l >> 2));
}

namespace std {
    template<class T1, class T2> struct hash<pair<T1, T2>> {
        size_t operator()(const pair<T1, T2>& p) const {
            return CombineHashes(hash<T1>()(p.first), hash<T2>()(p.second));
        }
    };

    template<class T> struct hash<vector<T>> {
        size_t operator()(const vector<T>& v) const {
            size_t res = -1;
            for (const auto& it : v) res = CombineHashes(res, it);
            return res;
        }
    };
}

template<class T> struct custom_hash : hash<T> {
    size_t operator()(const T& t) const {
        static const uint64_t C = (uint64_t)(4e18 * acos(0)) | 71;
        return __builtin_bswap64((hash<T>::operator()(t) ^ RANDOM_SEED) * C);
        //uint64_t x = hash<T>::operator()(t) + 0x9e3779b97f4a7c15;
        //x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        //x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        //return x ^ (x >> 31) ^ RANDOM_SEED;
    }
};

template<class T> struct Xorshift {
    typedef T result_type;
    constexpr T min() { return 1; }
    constexpr T max() { return -1; }
    virtual T operator()() = 0;
    template<class It, class N> void fill(It b, It e, N l, N u) {
        uniform_int_distribution<N> d(l, u);
        for (; b != e; *b++ = d(*this));
    }
    template<class C, class N> void fill(C& c, N l, N u) {
        fill(begin(c), end(c), l, u);
    }
};

struct Xorshift32 : Xorshift<uint32_t> {
    result_type operator()() {
        static result_type s = XORSHIFT_SEED;
        s ^= s << 13;
        s ^= s >> 17;
        return s ^= s << 5;
    }
} gen;

struct Xorshift64 : Xorshift<uint64_t> {
    result_type operator()() {
        static result_type s = XORSHIFT_SEED;
        s ^= s << 13;
        s ^= s >> 7;
        return s ^= s << 17;
    }
} lgen;

struct _ {
    _() {
        ios_base::Init();
        cin.sync_with_stdio(0);
        cout.sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(6);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    }

    ~_() {
        cerr << fixed << setprecision(3) << "\nTime = ";
        cerr << (chrono::duration<double>(chrono::steady_clock::now() - START_TIME)).count() << '\n';
    }
} _;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 1.01e9;
const long long LINF = 4.1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;



template<class num, num MOD_, num PRIMITIVE_ROOT, uint8_t MAX_SIZE_LB>
struct NTT {
    NTT() {
        num r = binpow(PRIMITIVE_ROOT, MOD >> MAX_SIZE_LB);
        num root[] = {r, binpow(r, MOD - 2)};
        for (size_t i = 0, n = 1 << MAX_SIZE_LB, j; i < 2; ++i)
            for (rootPows[i][0] = 1, j = 1; j < n; ++j)
                rootPows[i][j] = prod(rootPows[i][j - 1], root[i]);
        twoPowsInv[0] = 1; twoPowsInv[1] = binpow(2, MOD - 2);
        for (size_t i = 2; i <= MAX_SIZE_LB; ++i)
            twoPowsInv[i] = prod(twoPowsInv[i - 1], twoPowsInv[1]);
    }

    void ntt(vector<num>& a, bool inv = false) const {
        size_t n = a.size();
        for (size_t i = 1, j = 0, bit; i < n; ++i) {
            bit = n >> __builtin_ctz(i); j -= n - bit - (bit >> 1);
            //for (bit = n >> 1; j >= bit; j -= bit, bit >>= 1); j += bit;
            if (i < j)
                swap(a[i], a[j]);
        }
        for (size_t len = 2, len2 = 1, ilen = 1 << MAX_SIZE_LB - 1; len <= n; len <<= 1, len2 <<= 1, ilen >>= 1)
            for (size_t i = 0; i < n; i += len)
                for (size_t j = 0, k = 0; j < len2; ++j, k += ilen) {
                    num u = a[i + j], v = prod(a[i + j + len2], rootPows[inv][k]);
                    a[i + j] = u + v < MOD ? u + v : u + v - MOD;
                    a[i + j + len2] = u >= v ? u - v : u - v + MOD;
                }
        if (inv) {
            num nInv = twoPowsInv[__builtin_ctz(n)];
            for (size_t i = 0; i < n; ++i)
                a[i] = prod(a[i], nInv);
        }
    }

    void mult(vector<num>& a, vector<num>& b, vector<num>& res) const {
        if (a.empty() || b.empty()) {
            res.resize(0);
            return;
        }
        size_t sa = a.size(), sb = b.size();
        size_t s = sa + sb - 1;
        size_t n = 1 << (31 - __builtin_clz(s));
        n <<= (n != s);
        a.resize(n);
        fill(a.begin() + sa, a.end(), 0);
        ntt(a);
        b.resize(n);
        fill(b.begin() + sb, b.end(), 0);
        ntt(b);
        res.resize(n);
        for (size_t i = 0; i < n; ++i)
            res[i] = prod(a[i], b[i]);
        for (ntt(res, true), res.resize(s); res.size() > 1 && res.back() == 0; res.pop_back());
    }

    num binpow(num x, num n) const {
        num res = 1;
        for (; n; n >>= 1, x = prod(x, x))
            if (n & 1)
                res = prod(res, x);
        return res;
    }

    static const num MOD = MOD_;
    num rootPows[2][1 << MAX_SIZE_LB], twoPowsInv[MAX_SIZE_LB + 1];

     // prod in long long:
     //     int, 998244353, 3, 23
     //     uint32_t, 2130706433, 3, 24
     //     long long, 2998927361, 3, 22
     // prod in uint64_t
     //     long long, 4253024257, 5, 23
     // prod in long double and long long
     //     long long, 838488366986035201, 11, 23
     // prod in long double and uint64_t
     //     uint64_t, 1676976733963681793, 3, 23
     // prod in __int128_t:
     //     long long, 4611686018326724609, 3, 25
     //     uint64_t, 9223372036737335297, 3, 24
     //     __int128_t, 13043817825309818881, 14, 23
     // prod in __uint128_t:
     //     __uint128_t, 18446744073692774401, 43, 24

    inline num prod(num a, num b) const {
        return (uint64_t)a * b % MOD;
        //return (a * b - ((long long)((ld)a * (ld)b / (ld)MOD) - 5) * MOD) % MOD;
    }
};


typedef ll num;
NTT<num, 838488366986035201, 11, 23> ntt;
const num MOD2 = 1009;


void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vi cnt(m);
    for (int i = 0, re; i < n; ++i) {
        cin >> re;
        ++cnt[re - 1];
    }
    multimap<int, vector<num>> pols;
    for (int i = 0; i < m; ++i)
        if (cnt[i])
            pols.emplace(cnt[i], vector<num>(cnt[i] + 1, 1));
    while (pols.size() > 1) {
        vector<num> a[2];
        for (int i = 0; i < 2; ++i) {
            a[i] = move(pols.begin()->second);
            pols.erase(pols.begin());
        }
        auto& res = a[0];
        ntt.mult(a[0], a[1], res);
        for (int i = 0; i < res.size(); ++i)
            res[i] %= MOD2;
        pols.emplace(res.size(), move(res));
    }

    cout << pols.begin()->second[k] << endl;
}


int main() {
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
