TJOI2018出CF原题弱化版是不是有点太过分了？对，就是 TJOI2018 教科书般的*
然而我这个问题只会那个题的范围的m^3做法
回忆一下1到n求和是二次的，平方求和公式是三次的，立方求和公式是四次的，那m次方求和公式一定是个m+1次多项式
直接扔m+2个值进去把它插出来，因为是连续的可以做到线性(不算逆元)
#include<cstdio>
const int N=1e6+,mod=1e9+;
int n,k,ans,sum,fac[N],pre[N],suf[N];
int Qpow(int x,int k)
{
if(k<=) return k?x:;
int tmp=Qpow(x,k>>);
return 1ll*tmp*tmp%mod*((k&)?x:)%mod;
}
int main()
{
scanf("%d%d",&n,&k);
fac[]=pre[]=suf[k+]=;
for(int i=;i<=k+;i++) fac[i]=1ll*fac[i-]*i%mod;
for(int i=;i<=k+;i++) pre[i]=1ll*pre[i-]*(n-i+mod)%mod;
for(int i=k+;i;i--) suf[i]=1ll*suf[i+]*(n-i+mod)%mod;
for(int i=;i<=k+;i++)
{
sum=(sum+Qpow(i,k))%mod;
int fz=1ll*pre[i-]*suf[i+]%mod;
int fm=1ll*fac[i-]*fac[k+-i]%mod;
(ans+=1ll*sum*fz%mod*Qpow(((k-i)&)?mod-fm:fm,mod-)%mod)%=mod;
}
printf("%d",ans);
return ;
}