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

//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i=0;i<e;++i)
#define forsn(i,s,e) for(int i=s;i<e;++i)
#define rforn(i,s) for(int i=s;i>=0;--i)
#define rforsn(i,s,e) for(int i=s;i>=e;--i)
#define int long long int
#define bitcount(a) __builtin_popcount(a) // set bits (add ll)
#define ln '\n'
#define getcurrtime() cerr<<"Time = "<<((double)clock()/CLOCKS_PER_SEC)<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inputfile freopen("input.txt", "r", stdin)
#define outputfile freopen("output.txt", "w", stdout)
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cerr<<endl; }
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << "\t"; err(++it, args...);
}
template<typename T1,typename T2>
ostream& operator <<(ostream& c,pair<T1,T2> &v){
	c<<"("<<v.fi<<","<<v.se<<")"; return c;
}
template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& out,TT<T...>& c){
    out<<"{ ";
    forstl(x,c) out<<x<<" ";
    out<<"}"; return out;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM=1e5+5,MOD=1e9+7;
const ld EPS = 1e-9;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod=1009;
// 998244353=1+7*17*2^23 : g=3
// 1004535809=1+479*2^21 : g=3
// 469762049=1+7*2^26 : g=3
// 7340033=1+7*2^20 : g=3
// For below change mult as overflow:
    // 10000093151233=1+3^3*5519*2^26 : g=5
    // 1000000523862017=1+10853*1373*2^26 : g=3
    // 1000000000949747713=1+2^29*3*73*8505229 : g=2
// For rest find primitive root using Shoup's generator algorithm
// root_pw: power of 2 >= maxn, Mod-1=k*root_pw => w = primitive^k 
template<long long Mod,long long root_pw,long long primitive>
struct NTT{
    inline long long powm(long long x,long long pw){
        x%=Mod;
        if(abs(pw)>Mod-1) pw%=(Mod-1);
        if(pw<0) pw+=Mod-1;
        ll res=1;
        while(pw){
            if(pw&1LL) res=(res*x)%Mod;
            pw>>=1;
            x=(x*x)%Mod;
        }
        return res;
    }
    inline ll inv(ll x){
        return powm(x,Mod-2); 
    }
    ll root,root_1;
    NTT(){
        root=powm(primitive,(Mod-1)/root_pw);
        root_1=inv(root);
    }
    void ntt(vector<long long> &a,bool invert){
        int n=a.size();
        for(long long i=1,j=0;i<n;i++){
            long long bit=n>>1;
            for(;j&bit;bit>>=1) j^=bit;
            j^=bit;
            if(i<j) swap(a[i],a[j]);
        }
        for(long long len=2;len<=n;len<<=1){
            long long wlen= invert ? root_1:root;
            for(long long i=len;i<root_pw;i<<=1) wlen=wlen*wlen%Mod;
            for(long long i=0;i<n;i+=len){
                long long w=1;
                for(long long j=0;j<len/2;j++){
                    long long u=a[i+j],v=a[i+j+len/2]*w%Mod;
                    a[i+j]= u+v<Mod ? u+v:u+v-Mod;
                    a[i+j+len/2]= u-v>=0 ? u-v:u-v+Mod;
                    w=w*wlen%Mod;
                }
            }
        }
        if(invert){
            ll n_1=inv(n);
            for(long long &x: a) x=x*n_1%Mod;
        }
    }
    vector<long long> multiply(vector<long long> const& a,vector<ll> const& b){
        vector<long long> fa(a.begin(),a.end()),fb(b.begin(),b.end());
        int n=1;
        while(n<a.size()+b.size()) n<<=1;
        point(fa,1,n);
        point(fb,1,n);
        for(int i=0;i<n;++i) fa[i]=fa[i]*fb[i]%Mod;
        coef(fa);
        return fa;
    }
    void point(vector<long long> &A,bool not_pow=1,int atleast=-1){
        if(not_pow){
            if(atleast==-1){
                atleast=1;
                while(atleast<A.size()) atleast<<=1;
            }
            A.resize(atleast,0);
        }
        ntt(A,0);
    }
    void coef(vector<long long> &A,bool reduce=1){
        ntt(A,1);
        if(reduce) while(A.size() and A.back()==0) A.pop_back(); 
    }
    void point_power(vector<long long> &A,long long k){
        for(long long &x: A) x=powm(x,k);
    }
    void coef_power(vector<long long> &A,int k){
        while(A.size() and A.back()==0) A.pop_back();
        int n=1;
        while(n<k*A.size()) n<<=1;
        point(A,1,n);
        point_power(A,k);
        coef(A);
    }
    vector<long long> power(vector<long long> a,ll p){
        while(a.size() and a.back()==0) a.pop_back();
        vector<long long> res;
        res.pb(1);
        while(p){
            if(p&1) res=multiply(res,a);
            a=multiply(a,a);
            p/=2;
        }
        return res;
    }
};
NTT<mod,1<<4,11> ntt;



signed main(){
	fastio;

	int n,m,k;
	cin>>n>>m>>k;

	int a[m] = {0};
	forn(i,n){
		int x;
		cin>>x;
		a[x-1]++;
	}
	v64 v1;
	v1.pb(1);
	forn(i,m){
		v64 v2;
		forn(j,a[i]+1) v2.pb(1);
		v1 = ntt.multiply(v1,v2);
	}
	cout<<v1[k]<<ln;

	return 0;
}