#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
namespace {
const long long mod=998244353;
inline long long qpow(long long a,long long b){
long long ret=1;
while(b){
if(b&1) ret=ret*a%mod;
a=a*a%mod;b>>=1;
}return ret;
}
inline void up(long long &x){
if(x>=mod) x-=mod;
}
long long *rev[23],*wn[23];
inline void init(){
for(long long mid=1,lg=0;mid<(1<<21);mid<<=1,lg++){
wn[lg]=new long long[mid];
wn[lg][0]=1;
long long w=qpow(3,(mod-1)/(mid<<1));
for(long long k=1;k<mid;k++){
wn[lg][k]=wn[lg][k-1]*w%mod;
}
}
}
struct poly{
#define rep(i,l,r) for(long long i=l;i<=r;i++)
vector<long long> a;
inline poly(){}
inline poly(long long n){a.resize(n+1);}
inline void ntt(long long lim){
a.resize(lim);
long long len=__lg(lim);
if(rev[len]==nullptr){
rev[len]=new long long [lim];
for(long long i=1;i<lim;i++) rev[len][i]=rev[len][i>>1]>>1|((i&1)?(lim>>1):0);
}
//cerr<<"! lim : "<<lim<<endl;
for(long long i=0;i<lim;i++) if(rev[len][i]<i) swap(a[rev[len][i]],a[i]);
for(long long mid=1,lg=0;mid<lim;mid<<=1,lg++){
for(long long j=0;j<lim;j+=(mid<<1)){
for(long long k=0;k<mid;k++){
long long x=a[j+k],y=a[j+k+mid]*wn[lg][k]%mod;
a[j+k]=(x+y);if(a[j+k]>=mod) a[j+k]-=mod;
a[j+k+mid]=(x-y);if(a[j+k+mid]<0) a[j+k+mid]+=mod;
}
}
}
}
inline void intt(long long lim){
a.resize(lim);
reverse(a.begin()+1,a.end());
ntt(lim);
long long inv=qpow(lim,mod-2);
for(long long i=0;i<lim;i++) a[i]=a[i]*inv%mod;
}
inline long long& operator [](long long x){
return a[x];
}
inline poly operator +(const poly&b){
long long lim=max(a.size(),b.a.size());
poly c(lim-1);
rep(i,0,lim-1) c[i]=(a[i]+b.a[i]),up(c[i]);
return c;
}
inline poly operator -(const poly&b){
long long lim=max(a.size(),b.a.size());
poly c(lim-1);
rep(i,0,lim-1) c[i]=(a[i]-b.a[i]+mod),up(c[i]);
return c;
}
inline poly operator *(const poly&b){
poly c=b,d=(*this);
long long len=(long long)(c.a.size())-1+(long long)(d.a.size())-1;
long long lim=1;
while(lim<=len) lim<<=1;//lim -> x^{lim-1}
d.ntt(lim),c.ntt(lim);
rep(i,0,lim-1) c[i]=c[i]*d[i]%mod;//,cerr<<c[i]<<" ";cerr<<endl;
//cerr<<"OPK"<<endl;
c.intt(lim);
c.a.resize(len+1);
return c;
}
};
void poly_multiply(unsigned *a, int n, unsigned *b,int m, unsigned *c){
init();
poly A(n),B(m);
for(long long i=0;i<=n;i++) A[i]=a[i];
for(long long i=0;i<=m;i++) B[i]=b[i];
poly C=A*B;
for(long long i=0;i<=n+m;i++) c[i]=C[i];
}
}