#include<bits/stdc++.h> #define upf(i,n,k) for(int i=k;i<=n;i++) #define lowf(i,n,k) for(int i=n;i>=k;i--) #define Max(a,b,c) max(a,max(b,c)) #define Min(a,b,c) min(a,min(b,c)) #define ofile(N) freopen(N".in","r",stdin),freopen(N".out","w",stdout) #define ri register int #define ie inline #define ll long long using namespace std; const ll mod=1e9+9; int n,m,k,sum,res,ans[10001]; ie ll qpow(ll a,ll b,ll p) { if(b==0)return 1; else if(b%2==1) return a*qpow(a,b-1,p)%p; else { ll num=qpow(a,b/2,p)%p; return num*num%p; } } ie int read() { int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } ie void out(int a) { if(a>=10)out(a/10); putchar(a%10+'0'); } ie void dfs(int t,int z) { if(t==0) { sum=0; upf(i,k,1)sum+=ans[i]; if(sum!=n)return ; // upf(i,k,1)cout<<ans[i]<j<' '; // cout<<endl<<sum<<endl; // upf(i,k,1)qpow(ans[i],k,mod) upf(i,k,1)res+=qpow(ans[i],m,mod); return ; } upf(i,n,z) { // sum+=i; ans[t]=i; dfs(t-1,i); } } int main() { //ofile(""); // cout<<qpow(2,3,9); n=read(),k=read(),m=read(); dfs(k,1); cout<<res%mod; return 0; }