#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
const int maxlongint=2147483647;
const long long mo=1e9+7;
const int N=200005;
using namespace std;
long long mod[3]={469762049,998244353,1004535809},M=mod[0]*mod[1],W[3][N];
long long f[3][N],g[3][N],v[3][N],v_[N],jc[3][N],ny[3][N],inv[N];
int n,m,fn;
long long poww(long long x,long long y,int z)
{
long long s=1;
x%=mod[z];
for(;y;x=x*x%mod[z],y>>=1)
if(y&1) s=s*x%mod[z];
return s;
}
long long mul(long long x,long long y,long long mo)
{
long long s=0;
x%=mo;
for(;y;x=(x+x)%mo,y>>=1)
if(y&1) s=(s+x)%mo;
return s;
}
void NTT(long long *f,int type,int z)
{
for(int i=0,p=0;iif(ifor(int j=fn>>1;(p^=j)>=1);
}
for(int i=2;i<=fn;i<<=1)
{
int half=i>>1,pe=fn/i;
for(int j=0;jlong long w=!type?W[z][j*pe]:W[z][fn-j*pe];
for(int k=j;klong long x=f[k],y=f[k+half]*w%mod[z];
f[k]=(x+y)%mod[z],f[k+half]=(x-y+mod[z])%mod[z];
}
}
}
if(type)
{
long long ni=poww(fn,mod[z]-2,z);
for(int i=0;imod[z];
}
}
long long CRT(long long a0,long long