#include using namespace std; using Int = long long; const char newl = '\n'; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a void drop(const T &x){cout< vector read(size_t n){ vector ts(n); for(size_t i=0;i>ts[i]; return ts; } // MOD can be composite numbers template T mod_pow(T a,long long n,const T MOD){ using ll = long long; T res(1); while(n){ if(n&1) res=(ll)res*a%MOD; a=(ll)a*a%MOD; n>>=1; } return res; } // mod can be composite numbers template T order(T x,const T MOD){ static map> dp; static map phi; vector &ps=dp[MOD]; if(ps.empty()){ T res=MOD,n=MOD; for(T i=2;i*i<=n;i++){ if(n%i) continue; while(n%i==0) n/=i; res=res/i*(i-1); } if(n!=1) res=res/n*(n-1); phi[MOD]=res; for(T i=2;i*i<=res;i++){ if(res%i) continue; while(res%i==0) res/=i; ps.emplace_back(i); } if(res!=1) ps.emplace_back(res); } T res=phi[MOD]; for(T p:ps){ while(res%p==0){ if(mod_pow(x,res/p,MOD)!=1) break; res/=p; } } return res; } template struct Rint{ static T mod; static void set_mod(T nmod){mod=nmod;} T v; Rint():v(0){} Rint(signed v):v(v){} Rint(long long t){v=t%mod;if(v<0) v+=mod;} Rint pow(long long k){ Rint res(1),tmp(v); while(k){ if(k&1) res*=tmp; tmp*=tmp; k>>=1; } return res; } static Rint add_identity(){return Rint(0);} static Rint mul_identity(){return Rint(1);} Rint inv(){return pow(mod-2);} Rint& operator+=(Rint a){v+=a.v;if(v>=mod)v-=mod;return *this;} Rint& operator-=(Rint a){v+=mod-a.v;if(v>=mod)v-=mod;return *this;} Rint& operator*=(Rint a){v=1LL*v*a.v%mod;return *this;} Rint& operator/=(Rint a){return (*this)*=a.inv();} Rint operator+(Rint a) const{return Rint(v)+=a;} Rint operator-(Rint a) const{return Rint(v)-=a;} Rint operator*(Rint a) const{return Rint(v)*=a;} Rint operator/(Rint a) const{return Rint(v)/=a;} Rint operator-() const{return v?Rint(mod-v):Rint(v);} bool operator==(const Rint a)const{return v==a.v;} bool operator!=(const Rint a)const{return v!=a.v;} bool operator <(const Rint a)const{return v T Rint::mod; template ostream& operator<<(ostream &os,Rint m){os<>T; while(T--){ int v,x; cin>>v>>x; const int mod=v*x+1; using R = Rint; R::set_mod(mod); int r=2; while(order(r,mod)!=mod-1) r++; r=R(r).pow(v).v; vector as; for(int i=0;i