#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<auto&operator<<(ostream&o,pairp){return o<<"{"<auto&operator<<(ostream&o,sets){for(auto&e:s)o< auto&operator<<(ostream&o,priority_queueq){while(!q.empty())o<auto&operator<<(ostream&o,map&m){for(auto&e:m)o<auto&operator<<(ostream&o,vectorv){for(auto&e:v)o<void ashow(T t,A...a){cout< struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){} bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}}; template auto&operator<<(ostream&o,TRI&t){return o<<"{"< P; typedef pair pll; typedef TRI tri; typedef vector vi; typedef vector vl; typedef vector vvi; typedef vector vvl; typedef vector

vp; typedef vector vd; typedef vector vs; const int MAX_N = 32005; template T mod_add(const T a, const T b, const T mod){ return (a + b) % mod; } template T mod_mul(const T a, const T b, const T mod){ return a * b % mod; } template T mod_pow(T a, T b, const T mod){ T res = 1; while(b){ if(b & 1){ res = mod_mul(res, a, mod); } a = mod_mul(a, a, mod); b >>= 1; } return res; } template T mod_inv(T a, T mod){ T u[] = {a, 1, 0}, v[] = {mod, 0, 1}, t; while(*v){ t = *u / *v; swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]), swap(u[2] -= t * v[2], v[2]); } u[1] %= mod; return (u[1] < 0) ? (u[1] + mod) : u[1]; } bool flag; template T garner(const vector& a, vector p, const T mod){ const unsigned int sz = a.size(); vector kp(sz + 1, 0), rmult(sz + 1, 1); p.push_back(mod); for(unsigned int i = 0; i < sz; ++i){ T x = mod_mul(a[i] - kp[i], mod_inv(rmult[i], p[i]), p[i]); x = (x < 0) ? (x + p[i]) : x; for(unsigned int j = i + 1; j < sz + 1; ++j){ kp[j] = mod_add(kp[j], rmult[j] * x, p[j]); rmult[j] = mod_mul(rmult[j], p[i], p[j]); } } if(flag) return rmult[sz]; return kp[sz]; } vector prime; bool is_prime[MAX_N]; void sieve(int n){ for(int i=0;i<=n;i++){ is_prime[i] = true; } is_prime[0] = is_prime[1] = false; for(int i=2;i<=n;i++){ if(is_prime[i]){ prime.push_back(i); for(int j=2*i;j<=n;j+=i){ is_prime[j] = false; } } } } signed main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; sieve(32000); map mp; flag = true; rep(i,n){ int x, y; cin >> x >> y; if(x) flag = false; for(int p : prime){ if(y % p) continue; int mult = 1; do{ y /= p, mult *= p; }while(y % p == 0); mp[p].emplace_back(x % mult, mult); } if(y > 1) mp[y].emplace_back(x % y, y); } vl x, y; for(const auto& it : mp){ int a = 0, b = 0; for(const P& p : it.se){ if(a < p.se) a = p.se, b = p.fi; } for(const P& p : it.se){ if(p.fi != b % p.se){ cout << "-1\n"; return 0; } } x.pb(b), y.pb(a); } cout << garner(x, y, (long long)MOD) << "\n"; return 0; }