#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;
}