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 GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DECIMAL(n)  std::cout << std::fixed;std::cout << std::setprecision(n);
#define hell 1000000007
#define narak 998244353
#define PI 3.14159265358979323844
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define fi first 
#define se second
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))  
#define REVERSE(v) reverse(ALL(v))
#define endl "\n"
#define maxc(v) *max_element(ALL(v))
#define minc(v) *min_element(ALL(v))
#define sqr(a) (a)*(a)
#define GCD(m,n) __gcd(m,n)
#define LCM(m,n) m*(n/GCD(m,n))
#define inputarr(a,n) for(int xxx=0;xxx<n;++xxx) cin>>(a)[xxx]
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define sz(a) (int)a.size()
#define sl(a) (int)a.length()
#define invect(data,n,commands) for(int xxx = 0;xxx<n;xxx++){int tmp;cin>>tmp;data.pb(tmp);commands}
#define inset(data,n,commands) for(int xxx = 0;xxx<n;xxx++){int tmp;cin>>tmp;data.insert(tmp);commands}
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl
#define debug cerr<<"bhau"<<endl
#define between(n,a,b) (a<=n&&n<=b)
#define clamp(n,a,b) (((n)<(a))?(a):(((n)>(b))?(b):(n))) 

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC 

template<typename T, typename U> static inline void amin(T &x, U y) 
{ 
    if (y < x) 
        x = y; 
}
template<typename T, typename U> static inline void amax(T &x, U y) 
{ 
    if (x < y) 
        x = y; 
}

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

#define ll long long
#define ld long double 
#define pii std::pair<int, int> 
#define pll std::pair<ll, ll>  
#define vi vector<int>  
#define vvi vector<vi > 
#define vii vector<pii >
#define point complex<ll>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//primes for hashing 937,991,1013,1409,1741

std::ostream& operator<<(std::ostream& out,pii a)
{
	out<<a.fi<<" "<<a.se;
	return out;
}
std::ostream& operator<<(std::ostream& out,pll a)
{
	out<<a.fi<<" "<<a.se;
	return out;
}
std::istream& operator>>(std::istream& in,pii &a)
{
    in>>a.fi>>a.se;
    return in;
}
std::istream& operator>>(std::istream& in,pll &a)
{
    in>>a.fi>>a.se;
    return in;
}

using namespace std;
using namespace __gnu_pbds;
const int MOD = 1009;
struct mod_int {
    int val;
 
    mod_int(long long v = 0) {
        if (v < 0) v = v % MOD + MOD;
        if (v >= MOD) v %= MOD;
        val = v;
    }
 
    static int mod_inv(int a, int m = MOD) {
        // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
        int g = m, r = a, x = 0, y = 1;
 
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }
 
        return x < 0 ? x + m : x;
    }
 
    explicit operator int() const {
        return val;
    }
 
    mod_int& operator+=(const mod_int &other) {
        val += other.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
 
    mod_int& operator-=(const mod_int &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
        return x % m;
#endif
        // Optimized mod for Codeforces 32-bit machines.
        // x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit integer.
        unsigned x_high = x >> 32, x_low = (unsigned) x;
        unsigned quot, rem;
        asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (m));
        return rem;
    }
 
    mod_int& operator*=(const mod_int &other) {
        val = fast_mod((uint64_t) val * other.val);
        return *this;
    }
 
    mod_int& operator/=(const mod_int &other) {
        return *this *= other.inv();
    }
 
    friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
    friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
    friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
    friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
 
    mod_int& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
 
    mod_int& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
 
    mod_int operator++(int) { mod_int before = *this; ++*this; return before; }
    mod_int operator--(int) { mod_int before = *this; --*this; return before; }
 
    mod_int operator-() const {
        return val == 0 ? 0 : MOD - val;
    }
 
    bool operator==(const mod_int &other) const { return val == other.val; }
    bool operator!=(const mod_int &other) const { return val != other.val; }
 
    mod_int inv() const {
        return mod_inv(val);
    }
 
    mod_int pow(long long p) const {
        assert(p >= 0);
        mod_int a = *this, result = 1;
 
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            a *= a;
            p >>= 1;
        }
 
        return result;
    }
 
    friend ostream& operator<<(ostream &stream, const mod_int &m) {
        return stream << m.val;
    }
    friend istream& operator>>(istream &stream, mod_int &m) {
        return stream >> m.val;
    }
};
namespace NTT {
    vector<mod_int> roots = {0, 1};
    vector<int> bit_reverse;
    int max_size = -1;
    mod_int root;
 
    bool is_power_of_two(int n) {
        return (n & (n - 1)) == 0;
    }
 
    int round_up_power_two(int n) {
        while (n & (n - 1))
            n = (n | (n - 1)) + 1;
 
        return max(n, 1);
    }
 
    // Given n (a power of two), finds k such that n == 1 << k.
    int get_length(int n) {
        assert(is_power_of_two(n));
        return __builtin_ctz(n);
    }
 
    // Rearranges the indices to be sorted by lowest bit first, then second lowest, etc., rather than highest bit first.
    // This makes even-odd div-conquer much easier.
    void bit_reorder(int n, vector<mod_int> &values) {
        if ((int) bit_reverse.size() != n) {
            bit_reverse.assign(n, 0);
            int length = get_length(n);
 
            for (int i = 0; i < n; i++)
                bit_reverse[i] = (bit_reverse[i >> 1] >> 1) + ((i & 1) << (length - 1));
        }
 
        for (int i = 0; i < n; i++)
            if (i < bit_reverse[i])
                swap(values[i], values[bit_reverse[i]]);
    }
 
    void find_root() {
        max_size = 1 << __builtin_ctz(MOD - 1);
        root = 2;
 
        // Find a max_size-th primitive root of MOD.
        while (!(root.pow(max_size) == 1 && root.pow(max_size / 2) != 1))
            root++;
    }
 
    void prepare_roots(int n) {
        if (max_size < 0)
            find_root();
 
        assert(n <= max_size);
 
        if ((int) roots.size() >= n)
            return;
 
        int length = get_length(roots.size());
        roots.resize(n);
 
        // The roots array is set up such that for a given power of two n >= 2, roots[n / 2] through roots[n - 1] are
        // the first half of the n-th primitive roots of MOD.
        while (1 << length < n) {
            // z is a 2^(length + 1)-th primitive root of MOD.
            mod_int z = root.pow(max_size >> (length + 1));
 
            for (int i = 1 << (length - 1); i < 1 << length; i++) {
                roots[2 * i] = roots[i];
                roots[2 * i + 1] = roots[i] * z;
            }
 
            length++;
        }
    }
 
    void fft_iterative(int N, vector<mod_int> &values) {
        assert(is_power_of_two(N));
        prepare_roots(N);
        bit_reorder(N, values);
 
        for (int n = 1; n < N; n *= 2)
            for (int start = 0; start < N; start += 2 * n)
                for (int i = 0; i < n; i++) {
                    mod_int even = values[start + i];
                    mod_int odd = values[start + n + i] * roots[n + i];
                    values[start + n + i] = even - odd;
                    values[start + i] = even + odd;
                }
    }
 
    const int FFT_CUTOFF = 150;
 
    vector<mod_int> mod_multiply(vector<mod_int> left, vector<mod_int> right) {
        int n = left.size();
        int m = right.size();
 
        // Brute force when either n or m is small enough.
        if (min(n, m) < FFT_CUTOFF) {
            const uint64_t ULL_BOUND = numeric_limits<uint64_t>::max() - (uint64_t) MOD * MOD;
            vector<uint64_t> result(n + m - 1, 0);
 
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++) {
                    result[i + j] += (uint64_t) ((int) left[i]) * ((int) right[j]);
 
                    if (result[i + j] > ULL_BOUND)
                        result[i + j] %= MOD;
                }
 
            for (uint64_t &x : result)
                if (x >= MOD)
                    x %= MOD;
 
            return vector<mod_int>(result.begin(), result.end());
        }
 
        int N = round_up_power_two(n + m - 1);
        left.resize(N);
        right.resize(N);
 
        bool equal = left == right;
        fft_iterative(N, left);
 
        if (equal)
            right = left;
        else
            fft_iterative(N, right);
 
        mod_int inv_N = mod_int(N).inv();
 
        for (int i = 0; i < N; i++)
            left[i] *= right[i] * inv_N;
 
        reverse(left.begin() + 1, left.end());
        fft_iterative(N, left);
        left.resize(n + m - 1);
        return left;
    }
 
    vector<mod_int> mod_power(const vector<mod_int> &v, int exponent) {
        assert(exponent >= 0);
        vector<mod_int> result = {1};
 
        if (exponent == 0)
            return result;
 
        for (int k = 31 - __builtin_clz(exponent); k >= 0; k--) {
            result = mod_multiply(result, result);
 
            if (exponent >> k & 1)
                result = mod_multiply(result, v);
        }
 
        return result;
    }
 
    vector<mod_int> mod_multiply_all(const vector<vector<mod_int>> &polynomials) {
        if (polynomials.empty())
            return {1};
 
        struct compare_size {
            bool operator()(const vector<mod_int> &x, const vector<mod_int> &y) {
                return x.size() > y.size();
            }
        };
 
        priority_queue<vector<mod_int>, vector<vector<mod_int>>, compare_size> pq;
 
        for (auto &poly : polynomials)
            pq.push(poly);
 
        while (pq.size() > 1) {
            vector<mod_int> a = pq.top(); pq.pop();
            vector<mod_int> b = pq.top(); pq.pop();
            pq.push(mod_multiply(a, b));
        }
 
        return pq.top();
    }
}
void meowmeow321()
{
	int n,m,k;
	cin>>n>>m>>k;
	int a[n];
	inputarr(a,n);
	map<int,int> cnt;
	for (int i = 0; i < n; ++i) {
		cnt[a[i]]++;
	}
	vi dog;
	trav(z,cnt)dog.pb(z.se);
	vector<vector<mod_int>> polynomials;
	for (int i = 0; i < n; ++i) {
		vector<mod_int> poly;
		for (int j = 0; j <= dog[i]; ++j) {
			poly.pb(1);
		}
		polynomials.pb(poly);
	}
	cout<<NTT::mod_multiply_all(polynomials)[k]<<endl;
}
int main()
{
    FAST;
    int testcases=1;
    //cin>>testcases;
    for(int i=0;i<testcases;++i)
    {
    	meowmeow321();
    }
    cerr<<endl<<"Time Elasped : "<<elasped_time<<endl;
    return 0;
}
