#include typedef uint64_t u64; typedef int64_t i64; using namespace std; template struct modint{ u64 val; modint(i64 val_=0):val((val_%i64(mod)+i64(mod))%i64(mod)){} modint operator-(){ return (val==0)?0:mod-val; } modint operator+(modint rhs){ return modint(*this)+=rhs; } modint operator-(modint rhs){ return modint(*this)-=rhs; } modint operator*(modint rhs){ return modint(*this)*=rhs; } modint operator/(modint rhs){ return modint(*this)/=rhs; } modint operator^(i64 rhs){ return modint(*this)^=rhs; } modint &operator+=(modint rhs){ val+=rhs.val,val-=((val>=mod)?mod:0); return (*this); } modint &operator-=(modint rhs){ val+=((val>=1; } return (*this)=res; } bool operator==(modint rhs){ return val==rhs.val; } bool operator!=(modint rhs){ return val!=rhs.val; } friend std::ostream &operator<<(std::ostream& os,modint x){ return os<<(x.val); } friend std::istream &operator>>(std::istream& is,modint& x){ u64 t; is>>t,x=t; return is; } }; template struct NTT{ typedef modint mint; mint g; vector rev; NTT(){ for(g=2;;g+=1){ if((g^((mod-1)>>1))!=1){ return; } } } void dft(vector& f){ int siz=f.size(); for(int i=0;i operator()(vector a,vector b){ int cnt=0,siz=1,mxsiz=a.size()+b.size()-1; while(siz>1]>>1)+(1< struct comb{ vector dat,idat; comb(int mx=3000000):dat(mx+1,1),idat(mx+1,1){ for(int i=1;i<=mx;++i){ dat[i]=dat[i-1]*i; } idat[mx]/=dat[mx]; for(int i=mx;i>0;--i){ idat[i-1]=idat[i]*i; } } T operator()(int n,int k){ if(n<0||k<0||n ntt; typedef modint mint; comb com; vector conv1(vector a,mint T){ int n=a.size(); vector b(n),c(n); for(int i=0;i res(2*n-1); for(int i=0;i<2*n-1;++i){ res[i]=(d1[i]*(-T*2+1)+d2[i]*2*T)/com(2*n-2,i); } return res; } template vector> conv2(vector> a,vector> b,modint T){ int n=a.size(),m=b.size(); vector c(n),d(m); for(int i=0;i>N>>a>>b; T=mint(a)/b; vector> f(N); f[0]={0,1}; for(int i=1;i g={1}; for(int i=0;i