namespace Poly
{
int rev[N],limit;
inline void qmo(int &x){x+=(x>>31)&mod;}
inline int quick_pow(int x,int k){int res=1;for (;k;k>>=1,x=1ll*x*x%mod) if (k&1) res=1ll*res*x%mod;return res;}
inline void NTT_init(int size)
{
int l=0;limit=1;
while (limit<=size) limit<<=1,l++;
rep(i,0,limit-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
}
inline void NTT(int *A,int tp)
{
rep(i,0,limit-1) if (i<rev[i]) swap(A[i],A[rev[i]]);
for (int mid=1;mid<limit;mid<<=1)
{
int Wn=quick_pow(tp==1?3:quick_pow(3,mod-2),mod/(mid<<1));
for (int j=0;j<limit;j+=(mid<<1))
{
int w=1;
rep(k,0,mid-1)
{
int x=A[j+k],y=1ll*w*A[j+k+mid]%mod;
qmo(A[j+k]=x+y-mod);
qmo(A[j+k+mid]=x-y);
w=1ll*w*Wn%mod;
}
}
}
if (tp==-1)
{
int I=quick_pow(limit,mod-2);
rep(i,0,limit-1) A[i]=1ll*A[i]*I%mod;
}
}
inline void PolyInv(int *A,int *F,int n)
{
static int tmp[N];
if (n==1) return void(F[0]=quick_pow(A[0],mod-2));
int mid=(n+1)>>1; PolyInv(A,F,mid); NTT_init(n<<1);
rep(i,0,n-1) tmp[i]=A[i]; rep(i,n,limit-1) tmp[i]=0;
NTT(F,1),NTT(tmp,1);
rep(i,0,limit-1) F[i]=1ll*F[i]*(2-1ll*F[i]*tmp[i]%mod+mod)%mod;
NTT(F,-1);
rep(i,n,limit-1) F[i]=0;
}
}