#include<cstdio> #include<algorithm> #include<ctype.h> #include<cstring> #include<iostream> #include<vector> #include<queue> #include<ctime> #include<cmath> #include<queue> #include<map> #include<set> #include<unordered_map> #include<stack> #define pr pair<int,int> #define eps 1e-8 #define int long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } const int Mod=1e9+7; int dp[5005][5005]; int n,k,m,ans; int qpow(int base,int t) { int ret=1; while(t) { if(t&1) ret=ret*base%Mod; base=base*base%Mod; t>>=1; } return ret; } signed main() { n=read(),k=read(),m=read(); dp[0][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=((i>=j?dp[i-j][j]:0)+dp[i-1][j-1])%Mod; for(int i=1;i<=n;i++) { int awa=qpow(i,m); for(int j=1;j*i<=n&&j<=k;j++) ans=(ans+dp[n-j*i][k-j]*awa%Mod)%Mod; } printf("%lld\n",ans); return 0; }