#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<<" "< void chmax(t&a,u b){if(a void 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; } 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); } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); } 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; } int mask(int i){ return (int(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 random_device rd; static mt19937_64 gen(rd()); #endif return uniform_int_distribution(l, r)(gen); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } int gcd(int a,int b){return b?gcd(b,a%b):a;} int extgcd(int a,int b,int&x,int&y){ if(b==0){ x=1; y=0; return a; }else{ int g=extgcd(b,a%b,y,x); y-=a/b*x; return g; } } //x*y=g mod m //returns (g,y) pi modinv(int x,int m){ int a,b; int g=extgcd(x,m,a,b); if(a<0)a+=m/g; return pi(g,a); } //x = a mod b //x = c mod d // => x = p mod q //returns (-1,-1) when infeasible pi crt(int a,int b,int c,int d){ if(b z,int m){ int ans=0,w=1; rep(i,si(z)){ int x=z[i].a; ans=(ans+w*x)%m; rng(j,i+1,si(z)) z[j].a=(z[j].a+z[j].b-x%z[j].b)*modinv(z[i].b,z[j].b).b%z[j].b; w=(w*z[i].b)%m; } return ans; } template t pow_mod(t x,t n,t m){ t r=1; while(n){ if(n&1)r=(r*x)%m; x=(x*x)%m; n>>=1; } return r; } bool is_prime(ll n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; ll d = n - 1; while (d % 2 == 0) d /= 2; for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) { if (n <= a) break; ll t = d; ll y = pow_mod<__int128_t>(a, t, n); // over while (t != n - 1 && y != 1 && y != n - 1) { y = __int128_t(y) * y % n; // flow t <<= 1; } if (y != n - 1 && t % 2 == 0) { return false; } } return true; } ll pollard_single(ll n) { auto f = [&](ll x) { return (__int128_t(x) * x + 1) % n; }; if (is_prime(n)) return n; if (n % 2 == 0) return 2; ll st = 0; while (true) { st++; ll x = st, y = f(x); while (true) { ll p = gcd((y - x + n), n); if (p == 0 || p == n) break; if (p != 1) return p; x = f(x); y = f(f(y)); } } } vc pollard(ll n) { if (n == 1) return {}; ll x = pollard_single(n); if (x == n) return {x}; vc le = pollard(x); vc ri = pollard(n / x); le.insert(le.end(), ri.begin(), ri.end()); return le; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<>n; vc q; rep(i,n){ int a,b;cin>>a>>b; vi f=pollard(b); dmp(f); map vs; for(auto v:f){ if(vs.count(v)==0)vs[v]=1; vs[v]*=v; } for(auto kv:vs) q.eb(a%kv.b,kv.b); } sort(all(q),[](pi a,pi b){return a.b>b.b;}); dmp(q); vc z; for(auto p:q){ int a,b;tie(a,b)=p; bool found=false; for(auto&e:z){ int c,d;tie(c,d)=e; int g=gcd(b,d); if(g>1){ e=crt(a,b,c,d); if(e.a==-1){ print(-1); return 0; } found=true; break; } } if(!found)z.eb(a,b); } int ans=garner(z,1000000007); cout<