#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;