#include using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "< bool chmax(t&a,u b){if(a bool chmin(t&a,u b){if(b using vc=vector; template using vvc=vc>; using pi=pair; using vi=vc; template ostream& operator<<(ostream& os,const pair& p){ return os<<"{"< ostream& operator<<(ostream& os,const vc& v){ os<<"{"; for(auto e:v)os< void dmpr(ostream&os,const T&t,const Args&... args){ os< ostream& operator<<(ostream&os,const array&a){ return os<(all(a)); } template void print_tuple(ostream&,const T&){ } template void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<(t); print_tuple(os,t); } template ostream& operator<<(ostream&os,const tuple&t){ os<<"{"; print_tuple<0,tuple,Args...>(os,t); return os<<"}"; } template void print(t x,int suc=1){ cout<>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template void print(const pair&p,int suc=1){ print(p.a,2); print(p.b,suc); } template void print(const vector&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)< void mkuni(vc&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution(l, r)(gen); } template void myshuffle(vc&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } vvc readGraph(int n,int m){ vvc g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc readTree(int n){ return readGraph(n,n-1); } //mint107 は verify してねえ //#define DYNAMIC_MOD struct modinfo{uint mod,root; #ifdef DYNAMIC_MOD constexpr modinfo(uint m,uint r):mod(m),root(r),im(0){set_mod(m);} ull im; constexpr void set_mod(uint m){ mod=m; im=ull(-1)/m+1; } uint product(uint a,uint b)const{ ull z=ull(a)*b; uint x=((unsigned __int128)z*im)>>64; uint v=uint(z)-x*mod; return v struct modular{ static constexpr uint const &mod=ref.mod; static modular root(){return modular(ref.root);} uint v; //modular(initializer_listls):v(*ls.bg){} modular(ll vv=0){s(vv%mod+mod);} modular& s(uint vv){ v=vv>=1; } return res; } modular inv()const{return pow(mod-2);} /*modular inv()const{ int x,y; int g=extgcd(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return modular(x); }*/ friend modular operator+(int x,const modular&y){ return modular(x)+y; } friend modular operator-(int x,const modular&y){ return modular(x)-y; } friend modular operator*(int x,const modular&y){ return modular(x)*y; } friend modular operator/(int x,const modular&y){ return modular(x)/y; } friend ostream& operator<<(ostream&os,const modular&m){ return os<>(istream&is,modular&m){ ll x;is>>x; m=modular(x); return is; } bool operator<(const modular&r)const{return v void inplace_fmt(const int n,mint*const f,bool inv){ static constexpr uint mod=mint::mod; static constexpr uint mod2=mod*2; static constexpr int L=30; static mint g[L],ig[L],p2[L]; if(g[0].v==0){ rep(i,L){ mint w=-mint::root().pow(((mod-1)>>(i+2))*3); g[i]=w; ig[i]=w.inv(); p2[i]=mint(1<>=1){//input:[0,mod) rep(i,b){ uint x=f[i+b].v; f[i+b].v=f[i].v+mod-x; f[i].v+=x; } } if(b>>=1){//input:[0,mod*2) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*3) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*4) mint p=1; for(int i=0,k=0;i void inplace_fmt(vector&f,bool inv){ inplace_fmt(si(f),f.data(),inv); } //size of input must be a power of 2 //output elements are in the range [0,mod*4) template void half_fmt(const int n,mint*const f){ static constexpr uint mod=mint::mod; static constexpr uint mod2=mod*2; static const int L=30; static mint g[L],h[L]; if(g[0].v==0){ rep(i,L){ g[i]=-mint::root().pow(((mod-1)>>(i+2))*3); h[i]=mint::root().pow((mod-1)>>(i+2)); } } int b=n; int lv=0; if(b>>=1){//input:[0,mod) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*2) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*3) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*4) mint p=h[lv++]; for(int i=0,k=0;i void half_fmt(vector&f){ half_fmt(si(f),f.data()); } #ifdef USE_GOOD_MOD template vc multiply(vc x,const vc&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z(s); rep(i,si(y))z[i]=y[i]; inplace_fmt(z,false); rep(i,s)x[i]*=z[i]; }else{ rep(i,s)x[i]*=x[i]; } inplace_fmt(x,true);x.resize(n); return x; } template vc multiply_givenlength(vc x,const vc&y,bool same=false){ int s=si(x); assert(ispow2(s)); assert(si(y)); x.resize(s);inplace_fmt(x,false); if(!same){ vc z(s); rep(i,si(y))z[i]=y[i]; inplace_fmt(z,false); rep(i,s)x[i]*=z[i]; }else{ rep(i,s)x[i]*=x[i]; } inplace_fmt(x,true); return x; } #else //59501818244292734739283969-1=5.95*10^25 までの値を正しく計算 //最終的な列の大きさが 2^24 までなら動く //最終的な列の大きさが 2^20 以下のときは,下の 3 つの素数を使ったほうが速い(は?) //VERIFY: yosupo //Yukicoder No980 (same=true) namespace arbitrary_convolution{ constexpr modinfo base0{167772161,3};//2^25 * 5 + 1 constexpr modinfo base1{469762049,3};//2^26 * 7 + 1 constexpr modinfo base2{754974721,11};//2^24 * 45 + 1 //extern constexpr modinfo base0{1045430273,3};//2^20 * 997 + 1 //extern constexpr modinfo base1{1051721729,6};//2^20 * 1003 + 1 //extern constexpr modinfo base2{1053818881,7};//2^20 * 1005 + 1 using mint0=modular; using mint1=modular; using mint2=modular; template vc sub(const vc&x,const vc&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z(s);rep(i,si(x))z[i]=x[i].v; inplace_fmt(z,false); if(!same){ vc w(s);rep(i,si(y))w[i]=y[i].v; inplace_fmt(w,false); rep(i,s)z[i]*=w[i]; }else{ rep(i,s)z[i]*=z[i]; } inplace_fmt(z,true);z.resize(n); return z; } template vc multiply(const vc&x,const vc&y,bool same=false){ auto d0=sub(x,y,same); auto d1=sub(x,y,same); auto d2=sub(x,y,same); int n=si(d0); vc res(n); static const mint1 r01=mint1(mint0::mod).inv(); static const mint2 r02=mint2(mint0::mod).inv(); static const mint2 r12=mint2(mint1::mod).inv(); static const mint2 r02r12=r02*r12; static const mint w1=mint(mint0::mod); static const mint w2=w1*mint(mint1::mod); rep(i,n){ ull a=d0[i].v; ull b=(d1[i].v+mint1::mod-a)*r01.v%mint1::mod; ull c=((d2[i].v+mint2::mod-a)*r02r12.v+(mint2::mod-b)*r12.v)%mint2::mod; res[i].v=(a+b*w1.v+c*w2.v)%mint::mod; } return res; } template vc sub_givenlength(const vc&x,const vc&y,bool same=false){ int s=si(x); assert(ispow2(s)); assert(si(y)==s); vc z(s);rep(i,si(x))z[i]=x[i].v; inplace_fmt(z,false); if(!same){ vc w(s);rep(i,si(y))w[i]=y[i].v; inplace_fmt(w,false); rep(i,s)z[i]*=w[i]; }else{ rep(i,s)z[i]*=z[i]; } inplace_fmt(z,true); return z; } template vc multiply_givenlength(const vc&x,const vc&y,bool same=false){ auto d0=sub_givenlength(x,y,same); auto d1=sub_givenlength(x,y,same); auto d2=sub_givenlength(x,y,same); int n=si(d0); vc res(n); static const mint1 r01=mint1(mint0::mod).inv(); static const mint2 r02=mint2(mint0::mod).inv(); static const mint2 r12=mint2(mint1::mod).inv(); static const mint2 r02r12=r02*r12; static const mint w1=mint(mint0::mod); static const mint w2=w1*mint(mint1::mod); rep(i,n){ ull a=d0[i].v; ull b=(d1[i].v+mint1::mod-a)*r01.v%mint1::mod; ull c=((d2[i].v+mint2::mod-a)*r02r12.v+(mint2::mod-b)*r12.v)%mint2::mod; res[i].v=(a+b*w1.v+c*w2.v)%mint::mod; } return res; } } using arbitrary_convolution::multiply; using arbitrary_convolution::multiply_givenlength; #endif namespace integer_convolution{ extern constexpr modinfo base0{1045430273,3};//2^20 * 997 + 1 extern constexpr modinfo base1{1051721729,6};//2^20 * 1003 + 1 using mint0=modular; using mint1=modular; template vc sub(const vi&x,const vi&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z(s);rep(i,si(x))z[i]=x[i]; inplace_fmt(z,false); if(!same){ vc w(s);rep(i,si(y))w[i]=y[i]; inplace_fmt(w,false); rep(i,s)z[i]*=w[i]; }else{ rep(i,s)z[i]*=z[i]; } inplace_fmt(z,true);z.resize(n); return z; } vi multiply(const vi&x,const vi&y,bool same=false){ auto d0=sub(x,y,same); auto d1=sub(x,y,same); const mint1 r=mint1(mint0::mod).inv(); int n=si(d0); vi res(n); rep(i,n){ res[i]=d0[i].v+(r*(d1[i]-d0[i].v)).v*(ull)mint0::mod; } return res; } } //最大で 1< vc large_convolution(const vc&a,const vc&b,int mx){ int n=si(a),m=si(b); vc c(n+m-1); int len=1<<(mx-1); for(int i=0;i(a.bg+i,a.bg+i+x),vc(b.bg+j,b.bg+j+y)); rep(k,si(d)) c[i+j+k]+=d[k]; } } return c; } //Poly というのは常にサイズ 1 以上であることにしよう //low のあたりをかならずサイズ s のものを返すようにいじった //その影響で何かが起きているかも知れないし,起きていないかも知れない template struct Poly:public vc{ template Poly(Args...args):vc(args...){} Poly(initializer_listinit):vc(all(init)){} int size()const{ return vc::size(); } void ups(int s){ if(size()resize(s,0); } Poly low(int s)const{ assert(s); Poly res(s); rep(i,min(s,size()))res[i]=(*this)[i]; return res; } Poly rev()const{ auto r=*this; reverse(all(r)); return r; } Poly operator>>(int x)const{ assert(x Poly& operator+=(T t){ (*this)[0]+=t; return *this; } Poly& operator-=(const Poly&r){ ups(r.size()); rep(i,r.size()) (*this)[i]-=r[i]; return *this; } template Poly& operator-=(T t){ (*this)[0]-=t; return *this; } template Poly& operator*=(T t){ for(auto&v:*this) v*=t; return *this; } Poly& operator*=(const Poly&r){ return *this=multiply(*this,r); } Poly square()const{ return multiply(*this,*this,true); } #ifndef USE_GOOD_MOD Poly inv(int s)const{ Poly r{mint(1)/(*this)[0]}; for(int n=1;n f=low(2*n); f.resize(2*n); inplace_fmt(f,false); vc g=r.low(2*n); g.resize(2*n); inplace_fmt(g,false); rep(i,2*n)f[i]*=g[i]; inplace_fmt(f,true); rep(i,n)f[i]=0; inplace_fmt(f,false); rep(i,2*n)f[i]*=g[i]; inplace_fmt(f,true); rng(i,n,min(2*n,s))r[i]=-f[i]; } return r; } #endif template Poly& operator/=(T t){ return *this*=mint(1)/mint(t); } Poly quotient(const Poly&r,const Poly&rri)const{ int m=r.size(); assert(r[m-1].v); int n=size(); int s=n-m+1; if(s<=0) return {0}; return (rev().low(s)*rri.low(s)).low(s).rev(); } Poly& operator/=(const Poly&r){ return *this=quotient(r,r.rev().inv(max(size()-r.size(),int(0))+1)); } Poly& operator%=(const Poly&r){ *this-=*this/r*r; return *this=low(r.size()-1); } Poly operator+(const Poly&r)const{return Poly(*this)+=r;} template Poly operator+(T t)const{return Poly(*this)+=t;} Poly operator-(const Poly&r)const{return Poly(*this)-=r;} template Poly operator-(T t)const{return Poly(*this)-=t;} template Poly operator*(T t)const{return Poly(*this)*=t;} Poly operator*(const Poly&r)const{return Poly(*this)*=r;} template Poly operator/(T t)const{return Poly(*this)/=t;} Poly operator/(const Poly&r)const{return Poly(*this)/=r;} Poly operator%(const Poly&r)const{return Poly(*this)%=r;} Poly dif()const{ assert(size()); if(size()==1){ return {0}; }else{ Poly r(size()-1); rep(i,r.size()) r[i]=(*this)[i+1]*(i+1); return r; } } Poly inte(const mint invs[])const{ Poly r(size()+1,0); rep(i,size()) r[i+1]=(*this)[i]*invs[i+1]; return r; } //VERIFY: yosupo //opencupXIII GP of Peterhof H Poly log(int s,const mint invs[])const{ assert((*this)[0]==1); if(s==1)return {0}; return (low(s).dif()*inv(s-1)).low(s-1).inte(invs); } //Petrozavodsk 2019w mintay1 G //yosupo judge Poly exp(int s,const mint invs[])const{ return exp2(s,invs).a; } //2つほしいときはコメントアウトの位置ずらす pair exp2(int s,const mint invs[])const{ assert((*this)[0]==mint(0)); Poly f{1},g{1}; for(int n=1;;n*=2){ if(n>=s)break; g=g*2-(g.square()*f).low(n); //if(n>=s)break; Poly q=low(n).dif(); q=q+g*(f.dif()-f*q).low(2*n-1); f=f+(f*(low(2*n)-q.inte(invs))).low(2*n); } return make_pair(f.low(s),g.low(s)); } #ifndef USE_GOOD_MOD //CF250 E Poly sqrt(int s)const{ assert((*this)[0]==1); static const mint half=mint(1)/mint(2); Poly r{1}; for(int n=1;n f{1},g{1},z{1}; for(int n=1;n delta(2*n); rep(i,n)delta[n+i]=z[i]-freq(i)-freq(n+i); inplace_fmt(delta,false); vc gbuf(2*n); rep(i,n)gbuf[i]=g[i]; inplace_fmt(gbuf,false); rep(i,2*n)delta[i]*=gbuf[i]; inplace_fmt(delta,true); f.resize(2*n); rng(i,n,2*n)f[i]=-half*delta[i]; if(2*n>=s)break; z=f; inplace_fmt(z,false); vc eps=gbuf; rep(i,2*n)eps[i]*=z[i]; inplace_fmt(eps,true); rep(i,n)eps[i]=0; inplace_fmt(eps,false); rep(i,2*n)eps[i]*=gbuf[i]; inplace_fmt(eps,true); g.resize(2*n); rng(i,n,2*n)g[i]=-eps[i]; } f.resize(s); return f; } #endif pair divide(const Poly&r,const Poly&rri)const{ Poly a=quotient(r,rri); Poly b=*this-a*r; return make_pair(a,b.low(r.size()-1)); } //Yukicoder No.215 Poly pow_mod(int n,const Poly&r)const{ Poly rri=r.rev().inv(r.size()); Poly cur{1},x=*this%r; while(n){ if(n%2) cur=(cur*x).divide(r,rri).b; x=(x*x).divide(r,rri).b; n/=2; } return cur; } int lowzero()const{ rep(i,size())if((*this)[i]!=0)return i; return size(); } //VERIFY: yosupo Poly pow(int s,int p,const mint invs[])const{ assert(s>0); assert(p>0); int n=size(),z=0; for(;z=s)return Poly(s,0); mint c=(*this)[z],cinv=c.inv(); mint d=c.pow(p); int t=s-z*p; Poly x(t); rng(i,z,min(z+t,n))x[i-z]=(*this)[i]*cinv; x=x.log(t,invs); rep(i,t)x[i]*=p; x=x.exp(t,invs); rep(i,t)x[i]*=d; Poly y(s); rep(i,t)y[z*p+i]=x[i]; return y; } mint eval(mint x)const{ mint r=0,w=1; for(auto v:*this){ r+=w*v; w*=x; } return r; } }; //CF641 F2 //f*x^(-a) template struct Laurent{ Poly f; int a; Laurent(const Poly&num,const Poly&den,int s){ a=den.lowzero(); assert(a>a).inv(s)).low(s); } Laurent(const Poly&ff,int aa):f(ff),a(aa){} Laurent dif()const{ return Laurent(f*(-a)+(f.dif()<<1),a+1); } mint&operator[](int i){ assert(inc(0,i+a,si(f)-1)); return f[i+a]; } }; //source: Tellegen’s Principle into Practice //Yukicoder No.1145 //top には,(x-a[i]) の積が入っている(a がサイズ s に拡張されていることに注意) //なので例えば (1-a[i]x) の積が欲しい場合は, // Poly f=s.top; // Poly g(n+1); // rep(i,n+1)g[i]=f[si(f)-1-i]; template struct subproduct_tree{ using poly=Poly; int raws,s,h; mint*buf; vcf; vi len; poly top; void inner_product(const int n,const mint*a,const mint*b,mint*c){ rep(i,n)c[i]=a[i]*b[i]; } //first n elements are fft-ed //last n elements are raw data mod x^n-1 //the coefficient of x^n is v //convert the whole array into size-2n fft-ed array void doubling_fmt(const int n,mint*a,const mint v){ a[n]-=v*2; half_fmt(n,a+n); } subproduct_tree(const vc&a){ raws=si(a); s=1;while(s>__lg(i); f[i]=head; head+=len[i]*2; } } rep(i,s){ mint w=i1)doubling_fmt(len[i],f[i],1); } top.resize(s+1); rep(i,s)top[i]=f[1][s+i]; top[0]-=1; top[s]=1; } ~subproduct_tree(){ delete[] buf; } //VERIFY: yosupo vc multieval(const poly&b){ mint*buf2=new mint[s*2]; vc c(s*2); { mint*head=buf2; rng(i,1,s*2){ if((i&(i-1))==0&&__lg(i)%2==0)head=buf2; c[i]=head; head+=len[i]; } } { poly tmp=top.rev().inv(si(b)).rev()*b; rep(i,s)c[1][i]=i tmp(s); rng(i,1,s){ inplace_fmt(len[i],c[i],false); rep(k,2){ tmp.resize(len[i]); rep(j,len[i])tmp[j]=f[i*2+(k^1)][j]*c[i][j]; inplace_fmt(tmp,true); rep(j,len[i]/2)c[i*2+k][j]=tmp[len[i]/2+j]; } } vc ans(raws); rep(i,raws)ans[i]=c[s+i][0]; delete[] buf2; return ans; } poly interpolate(const vc&val){ mint*buf2=new mint[s*2*2]; vc c(s*2); { mint*head=buf2; rng(i,1,s*2){ if((i&(i-1))==0&&__lg(i)%2==0)head=buf2; c[i]=head; head+=len[i]*2; } } { vc z=multieval(poly(top.bg+(s-si(val)),top.ed).dif()); rep(i,s){ mint w=i1)doubling_fmt(len[i],c[i],0); } poly res(c[1]+s+(s-si(val)),c[1]+s*2); delete[] buf2; return res; } }; template vc multieval(const Poly&f,const vc&x){ return subproduct_tree(x).multieval(f); } template Poly interpolate(const vc&x,const vc&y){ assert(si(x)==si(y)); if(si(x)==1)return {y[0]}; subproduct_tree tree(x); return tree.interpolate(y); } //a==-1 だけ verify されてる //LOJ 6703 //product of ax+b template Poly product_linear(const vc>&rw){ mint w=1; vc buf; for(auto ab:rw){ if(ab.a==0){ w*=ab.b; }else{ w*=ab.a; buf.pb(-ab.b/ab.a); } } subproduct_tree tree(buf); const auto&f=tree.top; int n=si(buf)+1; vc res(n); rep(i,n)res[i]=f[si(f)-n+i]*w; return res; } #ifndef DYNAMIC_MOD extern constexpr modinfo base{998244353,3}; //extern constexpr modinfo base{1000000007,0}; //modinfo base{1,0}; #ifdef USE_GOOD_MOD static_assert(base.mod==998244353); #endif #else modinfo base(1,0); extern constexpr modinfo base107(1000000007,0); using mint107=modular; #endif using mint=modular; const int vmax=(1<<21)+10; mint fact[vmax],finv[vmax],invs[vmax]; void initfact(){ fact[0]=1; rng(i,1,vmax){ fact[i]=fact[i-1]*i; } finv[vmax-1]=fact[vmax-1].inv(); for(int i=vmax-2;i>=0;i--){ finv[i]=finv[i+1]*(i+1); } for(int i=vmax-1;i>=1;i--){ invs[i]=finv[i]*fact[i-1]; } } mint choose(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } mint binom(int a,int b){ return fact[a+b]*finv[a]*finv[b]; } mint catalan(int n){ return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } /* const int vmax=110; mint binbuf[vmax][vmax]; mint choose(int n,int k){ return binbuf[n-k][k]; } mint binom(int a,int b){ return binbuf[a][b]; } void initfact(){ binbuf[0][0]=1; rep(i,vmax)rep(j,vmax){ if(i)binbuf[i][j]+=binbuf[i-1][j]; if(j)binbuf[i][j]+=binbuf[i][j-1]; } } */ void slv(){ int n;cin>>n; map cnt; vi a=readvi(n); rep(i,n)cnt[a[i]]++; mint ans; for(auto [key,val]:cnt){ vc> buf; for(auto v:a){ buf.eb(1,key+v); if(v!=key){ buf.eb(1,key-v); } } auto f=product_linear(buf); auto g=f.inv(val); mint w=g[val-1]; w*=2; if((n-val+1)%2==0)w=-w; ans+=w; } print(ans); } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<>t;rep(_,t) slv(); }