#include <bits/stdc++.h> using namespace std; const long Mod=1e9+7; int n,k,m; long long ans; long long Pow[5005]; long long QPow(long long a,int b) { long long ans=1,tmp=a; while(b) { if(b&1) ans=(tmp*ans)%Mod; tmp=(tmp*tmp)%Mod; b>>=1; } return ans; } void DFS(int s,int p,long long v,long long last) { if(p==k) { if(s==n) ans=(ans+v)%Mod; return; } for(int i=last; i<=(n-s)-((k-p-1)*last); i++) DFS(s+i,p+1,(v+Pow[i])%Mod,i); //DFS(s+i,p+1,(v+QPow(i,m))%Mod,i); } int main() { scanf("%d%d%d",&n,&k,&m); Pow[0]=0; for(int i=1; i<=n; i++) Pow[i]=QPow(i,m); DFS(0,0,0,1); printf("%lld\n",ans); return 0; }