#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a struct Mint{ static constexpr T mod = MOD; T v; Mint():v(0){} Mint(signed v):v(v){} Mint(long long t){v=t%MOD;if(v<0) v+=MOD;} Mint pow(long long k){ Mint res(1),tmp(v); while(k){ if(k&1) res*=tmp; tmp*=tmp; k>>=1; } return res; } static Mint add_identity(){return Mint(0);} static Mint mul_identity(){return Mint(1);} Mint inv(){return pow(MOD-2);} Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;} Mint& operator/=(Mint a){return (*this)*=a.inv();} Mint operator+(Mint a) const{return Mint(v)+=a;}; Mint operator-(Mint a) const{return Mint(v)-=a;}; Mint operator*(Mint a) const{return Mint(v)*=a;}; Mint operator/(Mint a) const{return Mint(v)/=a;}; Mint operator-() const{return v?Mint(MOD-v):Mint(v);} bool operator==(const Mint a)const{return v==a.v;} bool operator!=(const Mint a)const{return v!=a.v;} bool operator <(const Mint a)const{return v dp; dp.reserve(sq); Mint res(1); for(int r=0;r0) return idx; } res*=p; } assert(0); return T(-1); } static Mint comb(long long n,int k){ Mint num(1),dom(1); for(int i=0;i constexpr T Mint::mod; template ostream& operator<<(ostream &os,Mint m){os< struct NTT{ static constexpr int md = bmds(X); static constexpr int rt = brts(X); inline int add(int a,int b){ a+=b; if(a>=md) a-=md; return a; } inline int mul(int a,int b){ return 1LL*a*b%md; } inline int pow(int a,int b){ int res=1; while(b){ if(b&1) res=mul(res,a); a=mul(a,a); b>>=1; } return res; } inline int inv(int x){ return pow(x,md-2); } vector > rts,rrts; void ensure_base(int n){ if((int)rts.size()>=n) return; rts.resize(n);rrts.resize(n); for(int i=1;i &a,bool f,int n=-1){ if(n==-1) n=a.size(); assert((n&(n-1))==0); for(int i=0,j=1;j+1>1;k>(i^=k);k>>=1); if(i>j) swap(a[i],a[j]); } for(int i=1;i multiply(vector as,vector bs){ int need=as.size()+bs.size()-1; int sz=1; while(sz f(sz),g(sz); for(int i=0;i<(int)as.size();i++) f[i]=as[i]; for(int i=0;i<(int)bs.size();i++) g[i]=bs[i]; ntt(f,0);ntt(g,0); for(int i=0;i rts={{0,0},{1,0}}; vector rev={0,1}; const dbl PI=acosl(-1.0); void ensure_base(int nbase){ if(nbase<=base) return; rev.resize(1<>1]>>1)+((i&1)<<(nbase-1)); rts.resize(1< &a,int n=-1){ if(n==-1) n=a.size(); assert((n&(n-1))==0); int zeros=__builtin_ctz(n); ensure_base(zeros); int shift=base-zeros; for(int i=0;i>shift)) swap(a[i],a[rev[i]>>shift]); for(int k=1;k fa; vector multiply(vector &a,vector &b){ int need=a.size()+b.size()-1; int nbase=0; while((1<(int)fa.size()) fa.resize(sz); for(int i=0;i>1);i++){ int j=(sz-i)&(sz-1); num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r; if(i!=j) fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r; fa[i]=z; } fft(fa,sz); vector res(need); for(int i=0;i struct SparseTable{ using F = function; vector > dat; vector ht; const F f; SparseTable(){} SparseTable(F f):f(f){} void build(const vector &v){ int n=v.size(),h=1; while((1<(n)); ht.assign(n+1,0); for(int j=2;j<=n;j++) ht[j]=ht[j>>1]+1; for(int j=0;j>n; vector as(n); for(int i=0;i>as[i]; using M = Mint; M ans{1}; int sum=0; for(int i=n-1;i>=0;i--){ ans*=M(as[i]).pow(sum); sum+=as[i]; } const int MAX = (1<<17)-1; vector bs(MAX,0); for(int a:as) bs[a]++; auto cs=FFT::multiply(bs,bs); for(int a:as) cs[a+a]--; for(int i=0;i<(int)cs.size();i++) ans*=M(i).pow(cs[i]/2); auto f=[](int a,int b){return min(a,b);}; SparseTable sp(f); sp.build(as); using D = long double; vector lg(MAX*2); for(int i=1;i