提交时间:2022-07-20 12:21:26
运行 ID: 52946
#include<bits/stdc++.h> #define mod 1000000007 #define ll long long #define N 5005 using namespace std; ll fpow(ll a,ll b){ if(!b) return 1; ll t(fpow(a,b>>1)); if(b&1) return t*t%mod*a%mod; return t*t%mod; } ll f[N][N],p[N][N]; int n,k;ll m,ans; int main(){ scanf("%d%d%d",&n,&k,&m); for(int i(1);i<=n+k;++i) p[i][1]=1; for(int i(1);i<=k;++i) p[0][i]=1; for(int i(1);i<=n+k;++i){ for(int j(2);j<=k;++j){ p[i][j]=p[i-1][j-1]%mod; if(i>=j) (p[i][j]+=p[i-j][j])%=mod; } } for(int s(1);s<=n;++s) f[s][s]=1; for(int i(2);i<=k;++i) for(int s(n);s>=i;--s) for(int j(s-i+1);j>=1;--j) f[s][j]=(f[s-j][j]+p[s-j][i-1])%mod; for(int i(1);i<=n-k+1;++i) ans=(ans+f[n][i]*fpow(i,m)%mod)%mod; printf("%lld\n",ans); return 0; }