#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1009
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define pb push_back
#define f first
#define s second
using namespace std;
#define PI acos(-1.0)
class point
{
public:
double x,y;
point(double _x=0,double _y=0){x=_x;y=_y;}
point operator+(const point &t)const{return point(x+t.x,y+t.y);}
point operator-(const point &t)const{return point(x-t.x,y-t.y);}
point operator*(const point &t)const{return point(x*t.x-y*t.y,x*t.y+y*t.x);}
void operator/=(const int n){x=x/n; y=y/n; return;}
point conj()const{return point(x,-y);}
double real()
{
return x;
}
};
#define base point
void fft(vector<base> &a,bool invert)
{
int n=a.size(),i,j;
for(i=1,j=0;i<n;++i) //Bit reverse
{
int bit=n>>1;
for(;j>=bit;bit>>=1)
j=j-bit;
j=j+bit;
if(i<j)
swap(a[i],a[j]);
}
for(int len=2;len<=n;len<<=1)
{
ld ang=2*PI/len*(invert?-1:1);
base wlen(cos(ang),sin(ang));
for(i=0;i<n;i+=len)
{
base w(1);
for(int j=0;j<len/2;++j)
{
base u=a[i+j],v=a[i+j+len/2]*w;
a[i+j]=u+v;
a[i+j+len/2]=u-v;
w=w*wlen;
}
}
}
if(invert)
{
for(i=0;i<n;++i)
a[i]/=n;
}
}
vector<ll> res;
void mul(const vector<ll> &a,const vector<ll> &b)
{
vector<base> fa(a.begin(),a.end()),fb(b.begin(),b.end());
size_t n=1;
int i;
while(n<max(a.size(),b.size())) n<<=1;
n<<=1;
fa.resize(n),fb.resize(n);
fft(fa,false);fft(fb,false);
for(i=0;i<n;++i)
{
fa[i]=(fa[i]*fb[i]);
}
fft(fa,true);
res.resize(n);
for(i=0;i<n;++i)
res[i]=(ll)(fa[i].real()+0.5);
}
void fft_modulo(const vector<ll> &a,const vector<ll> &b)
{
vector<ll> res1,res2,res3,res4,a1,a2,b1,b2;
ll s=ceil(sqrt(mod));
int i;
ll x;
for(i=0;i<a.size();++i)
{
x=a[i]%mod;
a1.pb(x%s);
a2.pb(x/s);
}
for(i=0;i<b.size();++i)
{
x=b[i]%mod;
b1.pb(x%s);
b2.pb(x/s);
}
mul(a1,b1);
res1=res;
res.clear();
mul(a1,b2);
res2=res;
res.clear();
mul(a2,b1);
res3=res;
res.clear();
mul(a2,b2);
res4=res;
for(i=0;i<res.size();++i)
{
res[i]=(res1[i]+ (((res2[i]+res3[i]))*s) + (((res4[i])*s))*s)%mod;
}
}
vector<ll> v[200001];
int a[400001],id[400001];
int main()
{
int n,m,k;
cin>>n>>m>>k;
set<pair<int,int> > st;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x]++;
}
for(int i=1;i<=m;i++)
{
if(a[i]>0)
{
st.insert(mp(a[i],i));
id[i]=i;
for(int j=0;j<=a[i];j++)v[i].pb(1);
}
}
while(st.size()>1)
{
int x=st.begin()->s;
st.erase(st.begin());
int y=st.begin()->s;
st.erase(st.begin());
// cerr<<x<<","<<y<<endl;
id[y]=id[x];
fft_modulo(v[x],v[y]);
v[x]=res;
a[x]+=a[y];
st.insert(mp(a[x],x));
}
int last=st.begin()->s;
cout<<(v[id[last]][k]%mod+mod)%mod;
return 0;
}