现在有时候做的题里带模数，如998244353。一般情况下开long long 就够了，但我写的程序一开long long就爆炸,开__int128才能过，但__int128又太慢了。

该模的地方都模了，求助，代码:

#include<cstdio>
#define S 5010
#define mod 998244353
using namespace std;
typedef long long ll;
ll l,r,s,type,pr[S],pl[S],fac[S];
ll str1[S][S];
inline ll read()
{
	ll x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}
void write(ll x){if(x>9)write(x/10);putchar(x%10+'0');}
ll qpow(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans%mod;
}
ll h(ll n,ll k){
	ll ans=0,y=0;
	pl[0]=pr[k+3]=fac[0]=1;
	for(int i=1;i<=k+2;i++)pl[i]=(pl[i-1]*(n-i))%mod,fac[i]=(fac[i-1]*i)%mod;
	for(int i=k+2;i>=1;i--)pr[i]=(pr[i+1]*(n-i))%mod;
	for(int i=1;i<=k+2;i++){
		y+=qpow(i,k);
		ll a=(pl[i-1]*pr[i+1])%mod;
		ll b=(fac[i-1]*((k-i)&1?(-1ll):1ll)*fac[k-i+2])%mod;
		ans=(ans+y*a%mod*qpow(b,mod-2))%mod;
	}
	return (ans+mod)%mod;
}
signed main(){
	l=read(),r=read(),s=read(),type=read();
	if(type==1){
		ll ans1=1,ans2=1;
		for(int i=r+s+1;i>=r;i--)ans1=(ans1*i)%mod;
		for(int i=l+s;i>=l-1;i--)ans2=(ans2*i)%mod;
		write((ans1-ans2+mod)%mod*qpow(s+2,mod-2)%mod);
	}
	else{
		ll ans=0;
		for(int i=0;i<=s+1;i++)
			str1[i][0]=((i==0)?1:0);
		for(int i=1;i<=s+1;i++)
			for(ll j=1;j<=i;j++)
				str1[i][j]=(str1[i-1][j-1]+(i-1)*str1[i-1][j]%mod)%mod;
		for(int k=0,p=qpow(-1,s+1);k<=s+1;k++)
			ans=(ans+p*str1[s+1][k]%mod*(h(r+s,k)-h((l-1+s),k)-qpow(2,k)*h((r+s)>>1,k)%mod+qpow(2,k)*h((l-1+s)>>1,k)%mod+mod)%mod)%mod,p*=-1;
		write(ans);
	}
}

输入:4721 186237 937 2

输出:233962283

谢谢!