#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define int ll const int maxn=1e5+10; const int mod=1e9+7; int n,m,k,ans; inline 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; } inline int fast_pow(int a,int b,int p) { int ans=1; for(; b; b>>=1,a=a*a%p) if(b&1) ans=ans*a%p; return ans; } inline void dfs(int n,int k,int sum,int ii) { if(k==0) { if(n!=0) return; else { ans=(ans+sum)%mod; // cout<<sum<<endl; return; } } for(int i=ii; i<=n/k; ++i) { int tmp=fast_pow(i,m,mod); // cout<<i<<' '; n-=i,--k; dfs(n,k,(sum+tmp)%mod,i); n+=i,++k; } } signed main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); n=read(),k=read(),m=read(); dfs(n,k,0,1); printf("%d\n",ans%mod); return 0; } /* 5 2 3 0 0 5 25 0 1 4 17 0 2 3 13 1 1 3 11 1 2 2 9 */