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

// Aimi Haraguni >> Konomi Suzuki >> Yui >>  Ikimono Gakari >> Garnidelia >> Kalafina... dude?
// Ztoking the best of the best
// Kirito >> Naofumi >> Yun Che >> Hao
// .... Sempre Amei Você ...
 
// Sempre amei você
// Mesmo de longe sem te ter
// Você me deu forças para viver
// E ser quem eu queria ser
// 
// 
// Você nunca verá uma menina como ela
// Mais linda em sentimentos que romance de novela
// Bela, ingênua, tipo como cinderela
// Sorte é do homem que estiver ao lado dela
// Guerreira, não compare com as demais
// Lutou muito para cumprir a exigência de seus pais
// Sua força vai além do que cê pensa ser capaz
// Essa menina não desiste daquilo que vai atrás, mas
// Eu fui tão cego pra não ver
// Que apenas ao meu lado ela queria viver
// Enquanto que por outra pessoa eu quis correr
// Ela não desistiu de mim mesmo eu a fazendo sofrer
// Que idiota, como eu não pude perceber?
// Que a menina que me amava estava sempre ali pra ver
// Eu sei que esse sentimento eu não mereço ter
// Mas desta vez eu vou tentar com meus erros aprender
//
// 
// Sempre amei você
// Mesmo de longe sem te ter
// Você me deu forças para viver
// E ser quem eu queria ser
// 
// 
// Ela sempre esteve lá, pra me ajudar
// Quando eu caí, me fez levantar
// Lutei tanto por meu sonho que sempre quis alcançar
// Que acabei ficando cego sem poder enxergar
// Eu nem consegui notar
// Que bem na minha frente era quem deveria amar
// Sempre achei que estava certo e que não podia errar
// Mas só mesmo quando perde pra então valorizar
// E eu perdi, e finalmente entendi
// Que quem eu procurava estava sempre ali
// Levou muito tempo pra ficha cair
// Como eu fui tapado, eu tenho que admitir
// Essa menina conseguiu me surpreender
// Seu olhar estava sempre além do que eu podia ver
// Eu tive que a perder, só pra perceber
// Que ao lado dela é onde eu quero viver
// 
// 
// Sempre amei você
// Mesmo de longe sem te ter
// Você me deu forças para viver
// E ser quem eu queria ser
// 
// 
// Eu tive que a perder
// Pra que pudesse perceber
// Que ao lado dela
// É onde eu quero viver
// Sim, um dia pode ser o fim
// Pode ser tarde demais e tudo acabar assim
// Mas pra ela eu vou dizer
// Não volto com minha palavra
// Com você quero viver
// 
// 
// Sempre amei você
// Mesmo de longe sem te ter
// Você me deu forças para viver
// E ser quem eu queria ser 


// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
 
#define pb push_back
#define ff  first
#define ss second
#define tm1 first
#define tm2 second.first
#define tm3 second.second
#define sz(x) ll(x.size())
#define fill(x, v) memset(x, v, sizeof(x))
#define all(v) (v).begin(), (v).end()
#define FER(i,a,b) for(ll i=ll(a); i< ll(b); ++i)
#define IFR(i,a,b) for(ll i=ll(a); i>=ll(b); --i )
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
 
#define N 6800005
#define mod1 1000000007
#define mod 1009
#define mod2 1000000009
#define bas 987625403
#define sqr(x) (x)*(x)  
#define INF 2000000000000000000

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ll, ii > tri;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> set_t;
 
#define trace(...) f(#__VA_ARGS__, __VA_ARGS__)
 
template<typename t> void f(const char* x, t&& val1){
    cout<<x<< " : "<<val1<<endl;
}
 
template<typename t1, typename... t2> void f(const char* x, t1&& val1, t2&&... val2){
    const char* xd=strchr(x+1, ',');
    cout.write(x, xd-x)<<" : "<<val1<<" | ";
    f(xd+1, val2...);
}


struct NTT{
    ll root_1, root, root_pw;
    inline ll bp(ll a, ll b){
        if(b==0) return 1;
        if(b&1) return (a*(bp(a, b-1)))%mod;
        ll x=bp(a, b>>1)%mod;
        return (x*x)%mod;;
    }
    inline ll inverse(ll a){
        return bp(a, mod-2);
    }
    inline void build(){
        ll cur_mod=mod-1;
        root_pw=1;
        while(cur_mod%2==0) cur_mod/=2, root_pw<<=1; 
        FER(i,2,1e5+1) if(bp(i, root_pw)==1){ root=i; break;}
        root_1=inverse(root);
    }
    inline void fft(vi &a , bool inv){
        ll n=sz(a);
        for(ll i=1, j=0; i<n; i++){
            ll bt=n>>1;
            for(; j&bt; bt>>=1) j^=bt;
            j^=bt;
            if(i<j) swap(a[i], a[j]);
        }
        for(ll len=2; len<=n; len<<=1){
            ll wlen=inv? root_1: root;
            for(ll i=len; i<root_pw; i<<=1) wlen=(sqr(wlen)%mod+mod)%mod;
            for(ll i=0; i<n; i+=len){
                ll w=1;
                for(ll j=0; j<len/2; j++){
                    ll 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+mod)%mod;
                }
            }
        }
        if(inv){
            ll n_1=inverse(sz(a));
            for(auto &xd: a) xd=((xd*n_1)%mod+mod)%mod;
        }
    }
    inline vi GetConvolution(vi a, vi b){
        ll n=1;
        while(n<sz(a)+sz(b)) n<<=1;
        a.resize(n), b.resize(n);
        fft(a, false), fft(b, false);
        FER(i,0,n) a[i]=((a[i]*b[i])%mod+mod)%mod;
        fft(a, true);
        while(a.back()==0) a.pop_back();
        return a;
    }
    inline vi BinPolyExp(vi &a, ll b){
        if(b==1) return a;
        ll n=1;
        while(n<sz(a)*b) n<<=1;
        a.resize(n);
        fft(a, false);
        for(auto &xd: a) xd=bp(xd, b);
        fft(a, true);
        while(a.back()==0) a.pop_back();
        return a;
    }
}ntt;

ll vis[1<<18], cnt[1<<18];
vector<vi> tnt;


inline vi solve(ll l, ll r){
    if(l+1==r) return tnt[l];
    if(l+2==r) return ntt.GetConvolution(tnt[l], tnt[l+1]);
    ll mid=(l+r)>>1;
    vi a=solve(l, mid);
    vi b=solve(mid, r);
    return ntt.GetConvolution(a, b);
}

int main(){
    fastio;
    ntt.build();
    ll n, m, k; cin>>n>>m>>k;
    FER(i,0,n){
        ll x; cin>>x;
        vis[x]++;
    }  
    FER(i, 1, 2e5+1) cnt[vis[i]]++;
    FER(i, 1, 2e5+1) {
        if(!cnt[i]) continue;
        vi froz;
        FER(j,0,i+1) froz.pb(1);
        froz=ntt.BinPolyExp(froz, cnt[i]);
        tnt.pb(froz);
    }
    vi ands=solve(0, sz(tnt));
    ll p=sz(ands)-k;
    assert(ands[sz(ands)-1]!=0);
    cout<<ands[p]<<endl;
    // vi x1, x2, x3;
    // x1.pb(1), x1.pb(2);
    // x2.pb(1), x2.pb(1);
    // x3=ntt.GetConvolution(x1, x2);
    // for(auto xd: x3) cout<<xd<<" "; cout<<endl;
    return 0;
}