金拱门全家桶

#define int long long
#define N 2000005
using namespace std;
namespace Polynomial{
	const int mod=998244353,g=3,ig=332748118,B=25000;
	inline void add(int&x,int y){(x+=y)>=mod?x-=mod:x;}
	int pwg[B+1],PWG[B+1],pwig[B+1],PWIG[B+1],inv[N],lg[N],pw[N];
	inline void Init(){
		for(int i=pwg[0]=1;i<=B;i++)pwg[i]=pwg[i-1]*g%mod;
		for(int i=PWG[0]=1;i<=B;i++)PWG[i]=PWG[i-1]*pwg[B]%mod;
		for(int i=pwig[0]=1;i<=B;i++)pwig[i]=pwig[i-1]*ig%mod;
		for(int i=PWIG[0]=1;i<=B;i++)PWIG[i]=PWIG[i-1]*pwig[B]%mod;
		for(int i=pw[0]=inv[1]=1;i<N;i++)pw[i]=pw[i-1]*2%mod;
		for(int i=2;i<N;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod,lg[i]=lg[i>>1]+1;
	}
	inline int qpow(int k){
		if(k==0)return 1;
		if(k>0)return PWG[k/B]*pwg[k%B]%mod;
		if(k<0)return PWIG[(-k)/B]*pwig[(-k)%B]%mod;
		return 114514;
	}
	inline int qpow(int b,int k){
		int s=1;
		while(k){
			if(k&1)s=s*b%mod;
			b=b*b%mod;k>>=1;
		}
		return s;
	}
	namespace NTT{
		inline void Complete(vector<int>&f,int len){
			while((int)f.size()<len)f.emplace_back(0);
		}
		inline void NTT(vector<int>&f,int t){
			if(f.size()==1)return;
			int n=f.size(),buf=1,G=qpow(t*(mod-1)/n);
			vector<int>l,r;l.resize(n>>1,0);r.resize(n>>1,0);
			for(int i=0;i<n>>1;i++)l[i]=f[i<<1],r[i]=f[i<<1|1];
			NTT(l,t);NTT(r,t);
			for(int i=0;i<n>>1;i++,buf=buf*G%mod){
				f[i]=(l[i]+buf*r[i]%mod)%mod;
				f[i+(n>>1)]=(l[i]+mod-buf*r[i]%mod)%mod;
			}
		}// NTT
		inline void Init(vector<int>&x,int len){
			int p=pw[lg[len]];
			while(p<len)p<<=1;
			Complete(x,p);
		}// Complete to 2^x
		inline vector<int>Convol(vector<int>a,vector<int>b){
			int len=a.size()+b.size(),p=pw[lg[len]];
			while(p<len)p<<=1;
			Complete(a,p);NTT(a,1);
			Complete(b,p);NTT(b,1);
			for(int i=0;i<p;i++)a[i]=a[i]*b[i]%mod;
			NTT(a,-1);
			for(int i=0;i<p;i++)a[i]=a[i]*inv[p]%mod;
			while(a.back()==0)a.pop_back();
			return a;
		}// Convolution
		inline vector<int>Inverse(vector<int>f){
			if(f.size()==1)return vector<int>(1,qpow(f[0],mod-2));
			int n=f.size(),p=pw[lg[n]];
			vector<int>hlf(n>>1,0);
			for(int i=0;i<n>>1;i++)hlf[i]=f[i];
			vector<int>g=Inverse(hlf);
			while(p<n<<1)p<<=1;
			Complete(f,p);NTT(f,1);
			Complete(g,p);NTT(g,1);
			for(int i=0;i<p;i++)g[i]=(2+mod-f[i]*g[i]%mod)%mod*g[i]%mod;
			NTT(g,-1);
			for(int i=n;i<p;i++)g[i]=0;
			for(int i=0;i<p;i++)g[i]=g[i]*inv[p]%mod;
			return g;
		}// Inverse
		inline vector<int>Exponential(vector<int>f){
			
		}
	}
	using namespace NTT;
	struct Poly{
		vector<int>f;
		Poly(int x=0){f=vector<int>(x);}
		Poly(vector<int>x=vector<int>(0)){f=x;}
		inline int size(){return f.size();}
		inline int&operator[](int x){return f[x];}
		inline Poly operator+(Poly b){
			Poly a=*this,ret(max(a.size(),b.size()));
			for(int i=0;i<(int)a.size();i++)add(ret[i],a.f[i]);
			for(int i=0;i<(int)b.size();i++)add(ret[i],b.f[i]);
			return ret;
		}
		inline Poly operator-(Poly b){
			Poly a=*this,ret(max(a.size(),b.size()));
			for(int i=0;i<(int)a.size();i++)add(ret[i],a.f[i]);
			for(int i=0;i<(int)b.size();i++)add(ret[i],mod-b.f[i]);
			while(ret.f.back()==0)ret.f.pop_back();
			return ret;
		}
		inline Poly operator*(Poly b){return(Poly)(Convol(f,b.f));}
		inline Poly operator*(int x){
			Poly ret=*this;
			for(int i=0;i<(int)ret.size();i++)ret[i]=ret[i]*x%mod;
			return ret;
		}
		inline Poly Derivative(){
			if(size()==0)return*this;
			Poly ret(size()-1);
			for(int i=0;i<(int)ret.size();i++)ret[i]=f[i+1]*(i+1)%mod;
			return ret;
		}// F'
		inline Poly Integral(){
			Poly ret(size()+1);
			for(int i=1;i<(int)ret.size();i++)ret[i]=f[i-1]*inv[i]%mod;
			return ret;
		}// ∫ F(x)dx
		inline Poly Ln(){
			Poly x=*this;Init(x.f,x.size());
			Poly deri=x.Derivative(),inve=Inverse(x.f),inte=deri*inve;
			return inte.Integral();
		}// ln(F)
		inline Poly Exp(){return Exponential(f);}// exp(F)
		inline Poly operator^(int k){return((*this).Ln()*k).Exp();}
		inline Poly operator^(Poly k){return((*this).Ln()*k).Exp();}// quick power
	};
}
using namespace Polynomial;