#include #include //#define DEBUG 0 using namespace std; typedef long long LL; typedef long double LD; typedef pair PII; typedef pair PLL; typedef pair PLDLD; typedef vector VI; typedef vector VLL; typedef vector VB; #define FOR(i,a,b) for(int i=(a);i<(int)(b);++i) #define REP(i,n) FOR(i,0,n) #define CLR(a) memset((a), 0 ,sizeof(a)) #define ALL(a) a.begin(),a.end() #define UNQ(a) a.erase(std::unique(ALL(a)),a.end()); #define endl "\n" const LD EPS=1e-10; const long long INFLL=(LL)(1e9)*(LL)(1e9); const int INF=1e9+7; template void chmin(T& a, const T b) { if(a>b) a=b; } template void chmax(T& a, const T b) { if(a struct has_iter { private: template static constexpr true_type check(typename U::iterator*); template static constexpr false_type check(...); public: static constexpr bool value = decltype(check(nullptr))::value; }; template void print(const T& container) { auto&& first=begin(container), last=end(container); auto&& back=prev(last); for(auto e=first; e!=last; e=next(e)) cout<<*e<<" \n"[e==back]; } extern void* enabler; template::value>::type*& = enabler> void print(const Head& head) { cout< void print(const string& container) { cout< void print(const Head& head, const Tail&... tail) { cout< void printd(const Args&... args) { #ifdef DEBUG print(args...); #endif } template void input(Head& head) { cin>>head; } template void input(Head& head, Tail&... tail) { cin>>head; input(tail...); } void io_speedup() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); } template istream& operator >> (istream& is, vector& vec) { for(T& x: vec) is >> x; return is; } template istream& operator >> (istream& is, pair& t) { is>>t.first>>t.second; return is; } template::type*& = enabler> void tuple_in(istream &is, tuple &t) { is>>get(t); } template::type*& = enabler> void tuple_in(istream &is, tuple &t) { is>>get(t); tuple_in(is, t); } template istream& operator >> (istream& is, tuple& t) { tuple_in<0, Ts...>(is, t); return is; } template ostream& operator << (ostream& os, const pair& t) { os<<'('<::type*& = enabler> void tuple_out(ostream &os,const tuple &t) { os<(t); } template::type*& = enabler> void tuple_out(ostream &os,const tuple &t) { os<(t)<<", "; tuple_out(os, t); } template ostream& operator << (ostream& os, const tuple& t) { os<<'('; tuple_out<0, Ts...>(os, t); os<<')'; return os; } template vector read(int n) { vector t(n); cin>>t; return t; } template T read() { T t; cin>>t; return t; } template struct vector_demensions { using type=vector::type>; }; template struct vector_demensions { using type=Head; }; template vector make_vectors(int size, T val) { return vector(size, val); } template auto make_vectors(int size, Args... tail) -> typename vector_demensions::type { auto val=make_vectors(forward(tail)...); return vector(size, val); } namespace Garner { /* Garnerのアルゴリズム x = mods[i].first mod mods[i].second を満たすxを求める https://qiita.com/drken/items/ae02240cd1f8edfc86fd */ using LL = long long; LL gcd(const LL a, const LL b) { return __gcd(a, b); } LL mod(const LL p, const LL m) { return (p<0)?(p%m+m):(p%m); } LL extgcd(const LL a, const LL b, LL &x, LL &y) { if(b==0) { x=1; y=0; return a; } LL d=extgcd(b, a%b, y, x); y-=a/b*x; return d; } LL modinv(const LL a, const LL m) { //a*x + m*y = gcd(a,m) = 1 LL x,y; extgcd(a, m, x, y); return mod(x, m); } /* Garnerの前処理 modが互いに素になるようにするor解が無いときは-1を返す */ vector> normalize(const vector> &mods) { vector> ret(mods); for(size_t i=0;i>(0); ret[i].second/=g; ret[j].second/=g; LL gi = gcd(ret[i].second, g); LL gj = g/gi; g = gcd(gi, gj); while(g != 1) { gi*=g; gj/=g; g = gcd(gi, gj); } ret[i].second*=gi; ret[j].second*=gj; ret[i].first%=ret[i].second; ret[j].first%=ret[j].second; } return ret; } LL Garner(const vector> &mods, const LL m) { const int n=mods.size(); vector modprod(n+1,1); vector p(n+1); for(int i=0;i> &mods, const LL m) { const vector> tmp(normalize(mods)); if(tmp.size() == 0) return -1; return Garner(tmp, m); } } int main() { int n; cin>>n; vector x(n); REP(i,n) input(x[i].first, x[i].second); auto tmp=Garner::normalize(x); if(tmp.size()==0) { print(-1);return 0; } LL ans=Garner::Garner(tmp, INF); bool f=accumulate(ALL(tmp), true, [](bool f,const PLL &r){return f&=r.first==0;}); if(f) { ans=1; for(auto&& e:tmp) (ans*=e.second)%=INF; print(ans); } else print(ans); }