记录编号	270020	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的求和问题	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.104 s
提交时间	2016-06-14 11:45:48	内存使用	7.92 MiB

#define maxn 500010ul

#include <stdio.h>

int n,k,s1,P[maxn],invf[maxn],fac[maxn],inv[maxn]; const int mod=998244353;

void read(register int &x){
	x=0; register int c=getchar(); for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar()) x=((x*10ll)+(c^48ll))%mod; return;
}

int power(int p,int k){
	if(p==-1){ if(k&1) return -1; else return 1; }
	int ret=1;
	while(k){
		if(k&1) ret=1ll*ret*p%mod;
		k>>=1,p=1ll*p*p%mod;
	} return ret;
}

int main(){
	freopen("Crazy_Sum.in","r",stdin);
	freopen("Crazy_Sum.out","w",stdout);
    read(n),read(k),n++,k++; fac[0]=inv[0]=inv[1]=invf[0]=1;
    for(int i=1;i<=k;i++) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=2;i<=k;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=k;i++) invf[i]=1ll*invf[i-1]*inv[i]%mod;
    for(int i=2;i<=k;i++) P[i]=(power(i-1,k-1)+P[i-1])%mod;
    if(n<=k) return printf("%d\n",P[n]),0;
    s1=n; for(int i=1;i<=k;i++) s1=1ll*s1*(n-i)%mod;
    int ans=0;
    for(int j=0;j<=k;j++) (ans+=1ll*power(-1,k-j)*P[j]%mod*s1%mod*invf[k-j]%mod*invf[j]%mod*power(n-j,mod-2)%mod)%=mod;
    printf("%d\n",(ans%mod+mod)%mod); return 0;
}