#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int n,m,k,a[5005]; long long ans; int read(){ register int res=0,w=1; register char ch=getchar(); while(ch<'0'||ch>'9'){ ch=='-'?w=-1:w=w; ch=getchar(); } while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+(ch^48),ch=getchar(); return res*w; } long long qpow(int x,int p,int d){ long long res=1; while(p){ if(p&1) res=(res*x)%d; x=x*x%d,p>>=1; } return res; } long long solve(){ long long res=0; for(register int i=0;i<k;i++) res+=qpow(a[i],m,mod);//,printf("%d ",a[i]); return res; } void dfs(int step,int cnt){ if(step==k) ans+=solve(); for(register int i=1;i<=cnt&&i<=floor(n/k);i++){ if(step==k-1){ a[step]=cnt,dfs(step+1,cnt-cnt),a[step]=0; break; } else { a[step]=i; dfs(step+1,cnt-i); a[step]=0; } } } int main(){ n=read(); k=read(); m=read(); dfs(0,n); printf("%lld",ans); return 0; }