622F - The Sum of the k-th Powers - CodeForces Solution

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define int long long
using namespace std;
inline int read(){
	int x=0; char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
const int N=1e6+600;
const int mod=1000000007;
int n,k;
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[N],ifac[N],pre[N],tt[N],vis[N],pri[N],val[N];
int tot;
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=(fac[i-1]*i)%mod;
	ifac[n]=ksm(fac[n],mod-2);
	ifac[0]=1;
	for(int i=n-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
	vis[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]) pri[++tot]=i,val[i]=ksm(i,k);
		for(int j=1;j<=tot&&pri[j]*i<=n;j++){
			vis[pri[j]*i]=1;
			val[pri[j]*i]=(val[pri[j]]*val[i])%mod;
			if(i%pri[j]==0) break ;
		}
	}
	val[1]=1;
	for(int i=1;i<=n;i++) val[i]=(val[i]+val[i-1])%mod;
}
int La(int n,int x){
	int ans=0;
	for(int i=1;i<=n;i++){
		int a=(pre[i-1]*tt[i+1]+mod)%mod;
		int b=ifac[i-1]*ifac[n-i]%mod;
		if((n-i)&1) b=(-b+mod)%mod;
		ans=(ans+a*b%mod*val[i]%mod)%mod;
	}
	return ans;
}
inline int Abs(int x){
	if(x<0) x=-x;
	return x;
}
signed main(){
	n=read(); k=read();
	init(k+2);
	pre[0]=tt[k+3]=1;
	for(int i=1;i<=k+2;i++) pre[i]=(pre[i-1]*(n-i+mod*2))%mod;
	for(int i=k+2;i>=1;i--) tt[i]=(tt[i+1]*(n-i+mod*2))%mod;
	//cout<<tt[k+2]<<" "<<tt[k+1]<<endl;
	/*for(int i=1;i<=k+2;i++){
		if(pre[i]<0) cout<<i<<endl;
		if(tt[i]<0) cout<<i<<endl;
	}*/
	int ans=La(k+2,n);
	cout<<ans<<endl;
	return 0;
}