#include #include using namespace std; using ull = unsigned long long; using ll = long long; using xy = pair; using coord = pair; using bs8 = bitset<8>; using bs16 = bitset<16>; using bs32 = bitset<32>; using bs64 = bitset<64>; using vl = vector; using vvl = vector; using vvvl = vector; using vd = vector; using vvd = vector; using vs = vector; using vvs = vector; using vxy = vector; using vvxy = vector; using vcoord = vector; using vvcoord = vector; #define rep(var, n) for (ll var = 0; var < (ll)(n); var++) #define cnt(var, n, m) for (ll var = (n); var <= (ll)(m); var++) #define rcnt(var, n, m) for (ll var = (n); var >= (ll)(m); var--) #define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++) #define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++) #define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl; #define ZINIT 1 #if __has_include("zout.h") #include "zout.h" #else namespace zz_print { class dbg { public: static bool unprint; static string margin; static string separated; static string indentS; static int hierarchical; static int topHier; static int precision; static bool exponential; static void setFloat(const int& prec, const bool& expo) { precision = prec; exponential = expo; }; template static void zout(Args&&... args) {}; }; bool dbg::unprint = false; string dbg::margin = ""; string dbg::separated = ""; string dbg::indentS = ""; int dbg::hierarchical = 0; int dbg::topHier = 0; int dbg::precision = 6; bool dbg::exponential = false; }; // namespace zz_print using namespace zz_print; #endif namespace zz_random { struct Xoshiro256 { ull s[4]; static inline ull rotl(ull x, int k) { return (x << k) | (x >> (64 - k)); } static inline ull splitmix64(ull& x) { ull z = (x += 0x9e3779b97f4a7c15ULL); z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL; z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL; return z ^ (z >> 31); } explicit Xoshiro256(ull seed = 1) { ull x = seed; rep(i, 4) s[i] = splitmix64(x); } inline ull next() { ull res = rotl(s[1] * 5, 7) * 9; ull t = s[1] << 17; s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3]; s[2] ^= t; s[3] = rotl(s[3], 45); return res; } inline ull operator()() { return next(); } /// integer [0, n) inline ll intn(const ll& n = 2) { return (ll)(next() % (ull)n); } /// integer [l, r] inline ll range(const ll& l, const ll& r) { return l + intn(r - l + 1); } /// real [0, 1) inline double real() { return (next() >> 11) * (1.0 / (1ULL << 53)); } inline double real(const double& r) { return real() * r; } inline double real(const double& l, const double& r) { return (l + real() * (r - l)); } // Box–Muller 用キャッシュ bool has_spare = false; double spare; /// 標準正規分布 N(0,1) inline double normal01() { if (has_spare) { has_spare = false; return spare; } double u = 0.0, v; while (u <= 0.0) u = real(); // (0,1) v = real(); double r = sqrt(-2.0 * log(u)); double theta = 2.0 * M_PI * v; spare = r * sin(theta); has_spare = true; return r * cos(theta); } /// 正規分布 N(mean, stddev^2) inline double normal(const double& mean, const double& stddev) { return mean + stddev * normal01(); } }; }; // namespace zz_random using namespace zz_random; xy gcdex(const ll a, const ll b) { xy ans; if (abs(a) < abs(b)) { ans = gcdex(b, a); swap(ans.first, ans.second); return ans; } else if (b == 0) { return xy{1, 0}; } // a > b // da x + db y = d // a x + b y = 1 // (b(a/b) + a%b) x + b y = 1 // b ((a/b)x + y) + a%b x = 1 // b x' + a%b y' = 1 // // |x| | 0 1 | |x'| // | | = | |*| | // |y| | 1 -a/b | |y'| // ans = gcdex(b, a % b); return xy{ans.second, ans.first - (a / b) * ans.second}; }; xy gcdex(const xy ab) { return gcdex(ab.first, ab.second); } ll gcd(const ll a, const ll b) { xy ans = gcdex(a, b); return abs(a * ans.first + b * ans.second); } ll gcd(const xy ab) { return gcd(ab.first, ab.second); } ll gcd(const vl& vec) { ll n = vec.size(); if (n == 0) return 1; if (n == 1) return vec[0]; vl subvec; rep(i, n / 2) subvec.push_back(gcd(vec[2 * i], vec[2 * i + 1])); if (n % 2) subvec.push_back(vec[n - 1]); return gcd(subvec); } ll lcm(const ll a, const ll b) { return (a * (b / gcd(a, b))); } ll lcm(const xy ab) { return lcm(ab.first, ab.second); } ll lcm(const vl& vec) { ll n = vec.size(); if (n == 0) return 1; if (n == 1) return vec[0]; vl subvec; rep(i, n / 2) subvec.push_back(lcm(vec[2 * i], vec[2 * i + 1])); if (n % 2) subvec.push_back(vec[n - 1]); return lcm(subvec); } xy ganner(const vxy& vec) { ll n = vec.size(); if (n == 0) return xy{-1, 0}; if (n == 1) return vec[0]; vxy subvec; rep(i, n / 2) { ll r1 = vec[2 * i].first, r2 = vec[2 * i + 1].first; ll p1 = vec[2 * i].second, p2 = vec[2 * i + 1].second; // p1 * x + p2 * y = d [%lcm(p1,p2)] // d*p1' * x + d*p2' * y = d [%(p1*p2/d)] // (d*p1' * x + d*p2' * y) * ((r2 - r1)/d) = d * ((r2 - r1)/d) [%(p1*p2/d)] // s * p1 * x + s * p2 * y = r2 - r1 [%(p1*p2/d)] // r1 + (s * x) * p1 = r2 - (s * p2) * y [%(p1*p2/d)] // // d*s = r2 - r1 [%p2] // s = (r2 - r1)/d [%(p2/d)] // x = d * 1 / p1 [%p2] // x = 1 / p1' [%p2] // x = inv(p1') [%p2] // x = inv(p1) [%(p2/d)] xy ans = gcdex(p1, p2); ll d = abs(p1 * ans.first + p2 * ans.second); ll mod = (p1 / d) * p2; if (((r2 - r1) % d) != 0) return xy{-1, 0}; ll s = (r2 - r1) / d; ll k = (s * ans.first) % (p2 / d); if (k < 0) k += p2 / d; xy pm = xy{k * p1 + r1, mod}; pm.first %= mod; if (pm.first < 0) pm.first += mod; subvec.push_back(pm); } if (n % 2) subvec.push_back(vec[n - 1]); return ganner(subvec); }; namespace zz_mod { template class pp { public: ll val; void flush() { val %= mod; if (val < 0) val += mod; }; void weak_flush() { if (val < 0) { val += mod; } else if (val >= mod) { val -= mod; } }; pp(ll x = 0) { val = x % mod; weak_flush(); }; friend std::ostream& operator<<(std::ostream& os, const pp& x) { return os << '{' << x.val << '|' << mod << '}'; }; pp& operator+=(const pp& p) { val += p.val; weak_flush(); return *this; }; pp& operator+=(ll x) { val += x % mod; weak_flush(); return *this; }; friend pp operator+(pp a, const pp& b) { return a += b; }; friend pp operator+(pp a, ll x) { return a += x; }; friend pp operator+(ll x, pp a) { return a += x; }; pp& operator-=(const pp& p) { val -= p.val; weak_flush(); return *this; }; pp& operator-=(ll x) { val -= x % mod; weak_flush(); return *this; }; friend pp operator-(pp a, const pp& b) { return a -= b; }; friend pp operator-(pp a, ll x) { return a -= x; }; friend pp operator-(ll x, const pp& a) { return pp(x) -= a; }; pp& operator*=(const pp& p) { val = (__int128)val * p.val; flush(); return *this; }; pp& operator*=(ll x) { val = (__int128)val * x; flush(); return *this; }; friend pp operator*(pp a, const pp& b) { return a *= b; }; friend pp operator*(pp a, ll x) { return a *= x; }; friend pp operator*(ll x, const pp& a) { return pp(x) *= a; }; pp inv() { xy ans = gcdex(mod, val); assert((mod * ans.first + val * ans.second) == 1); pp p(ans.second); return p; }; pp& operator/=(const pp& p) { return *this *= p.inv(); } pp& operator/=(ll x) { return *this *= gcdex(mod, x).second; } friend pp operator/(pp a, const pp& b) { return a /= b; }; friend pp operator/(pp a, ll x) { return a /= x; }; friend pp operator/(ll x, const pp& a) { a = a.inv(); return a /= x; }; pp exp(ll n) { if (n < 0) return inv().exp(-n); pp p = *this, ans(1); while (n > 1) { if (n & 1) ans *= p; p *= p; n >>= 1; } if (n > 0) ans *= p; return ans; }; }; } // namespace zz_mod using namespace zz_mod; namespace zz_prime { class prime { public: static vl sieves; static constexpr array pre_trial_division = array{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}; static void set(const ll n) { sieves = vl(n + 1, 1); ll i = 1; cnt(i, 2, n) { if (sieves[i] != 1) continue; ll j = i; j += i; while (j <= n) { if (sieves[j] == 1) sieves[j] = i; j += i; } } }; public: prime(const ll n) { set(n); } static void resize(const ll n) { if (sieves.size() < (n + 1)) set(n); } static bool millerRabin(const ll n) { if (n < 2) return false; if (n == 2) return true; if ((n % 2) == 0) return false; bool ans = false; vl a; if (n < 4759123141) { a = vl{2, 7, 61}; } else { a = vl{2, 325, 9375, 28178, 450775, 9780504, 1795265022}; } each(ite_a, a) { if ((*ite_a) >= n) break; ll d = n - 1; while ((d % 2) == 0) d >>= 1; ll x = 1; ll b = (*ite_a) % n; ll c = d; while (c > 0) { if (c & 1) x = ((__int128)x * b) % n; b = ((__int128)b * b) % n; c >>= 1; } if (x == 1 || x == (n - 1)) continue; bool OK = false; while (d < (n - 1)) { if (x == (n - 1)) { OK = true; break; } x = ((__int128)x * x) % n; d <<= 1; }; if (OK) continue; return false; } return true; } static bool isPrime(const ll x) { if (sieves.size() <= x) return millerRabin(x); if (x < 2) return false; return (sieves[x] == 1); } static vxy pollardsRho(ll x) { if (x < 2) return vxy(); vl prms; Xoshiro256 rnd; function F = [&rnd](ll x, const ll c, const ll m) -> ll { return (((__int128)x * x + c) % m); }; function Pollards = [&rnd, &F, &prms, &Pollards](const ll n) { if (n < 2) return; if (millerRabin(n)) { prms.push_back(n); return; } ll r = sqrtl(n); if ((r * r) == n) { Pollards(r); Pollards(r); return; } while (true) { ll a = rnd.range(2, n - 1); ll b = a; ll c = rnd.range(1, n - 1); ll d = 1; ll loopCnt = 0; do { loopCnt++; ll e = 1; ll k = 64; while (k > 0) { a = F(a, c, n); b = F(F(b, c, n), c, n); ll tmp = ((__int128)e * abs(a - b)) % n; if (tmp == 0) break; e = tmp; k--; } d = gcd(e, n); } while (d == 1 && loopCnt < 20); if (loopCnt >= 20) continue; if (d != n) { Pollards(d); Pollards(n / d); return; } } }; while ((x & 1) == 0) { x >>= 1; prms.push_back(2); } each(ite, pre_trial_division) { if (x < (*ite)) break; while ((x % (*ite)) == 0) { x /= (*ite); prms.push_back(*ite); } } Pollards(x); vxy ans; sort(prms.begin(), prms.end()); each(ite, prms) { if (ans.empty() || ans.back().first != (*ite)) { ans.emplace_back(*ite, 1); } else { ans.back().second++; } } return ans; } static vxy factor(ll x) { if (sieves.size() <= x) return pollardsRho(x); vl prms; if (x < 2) return vxy(); while (sieves[x] != 1) { prms.push_back(sieves[x]); x /= sieves[x]; } if (x != 1) prms.push_back(x); sort(prms.begin(), prms.end()); vxy ans; each(ite, prms) { if (ans.empty() || ans.back().first != (*ite)) { ans.emplace_back(*ite, 1); } else { ans.back().second++; } }; return ans; }; static vl divisor(const vxy& fac, const bool srt) { vl ans; function func = [&ans, &fac, &func](ll at, ll e) -> void { if (at == fac.size()) return; ll a = 1; cnt(i, 0, fac[at].second) { if (a != 1) ans.push_back(e * a); func(at + 1, e * a); a *= fac[at].first; } }; func(0, 1); if (srt) sort(ans.begin(), ans.end()); return ans; } static vl divisor(const ll n, const bool srt) { return divisor(factor(n), srt); } }; vl prime::sieves; } // namespace zz_prime using namespace zz_prime; ///////////////////////////////////////////////// namespace zz_poly { ll resize_2exp(vl& a) { ll nb = 0; while ((1 << nb) < a.size()) nb++; a.resize(1 << nb, 0); return nb; } template ll getFFTroot(ll len, bool rvs = false) { pp w; switch (mod) { case 880803841: // w = pp(26).exp(105).val; w = pp(26); break; case 897581057: // w = pp(3).exp(107).val; w = pp(3); break; case 998244353: // w = pp(3).exp(119).val; w = pp(3); break; default: assert("convolution nomatch mod" == ""); } if (rvs) return w.inv().exp((mod - 1) / len).val; return w.exp((mod - 1) / len).val; } template vl tran(const vl& vec, ll zeta) { ll n = vec.size(); if (n == 1) return vec; vl subvec1, subvec2; rep(i, n / 2) { subvec1.push_back(vec[2 * i]); subvec2.push_back(vec[2 * i + 1]); } vl SUBVEC1 = tran(subvec1, (zeta * zeta) % mod); vl SUBVEC2 = tran(subvec2, (zeta * zeta) % mod); ll w = 1; vl ans(n); rep(i, n) { ans[i] = (SUBVEC1[i % (n / 2)] + SUBVEC2[i % (n / 2)] * w) % mod; w = (w * zeta) % mod; } return ans; } template vl fft(vl& a) { resize_2exp(a); ll w = getFFTroot(a.size(), false); return tran(a, w); } template vl fft_reverse(vl& A) { resize_2exp(A); ll n = A.size(); ll w = getFFTroot(n, true); vl a = tran(A, w); rep(i, n) a[i] = (pp(a[i]) / n).val; return a; } template vl convolution(vl& a, vl& b) { ll n = a.size() + b.size() - 1; a.resize(n); b.resize(n); resize_2exp(a); resize_2exp(b); n = a.size(); // dbg::zout(getFFTroot(a.size(), false), pp(getFFTroot(a.size(), false)).exp(a.size()), // pp(getFFTroot(a.size(), false)).exp(a.size() / 2)); // dbg::zout(getFFTroot(a.size(), true), pp(getFFTroot(a.size(), true)).exp(a.size()), // pp(getFFTroot(a.size(), true)).exp(a.size() / 2)); dbg::zout("convolution a =", a); dbg::zout("convolution b =", b); vl A = fft(a); vl B = fft(b); dbg::zout("convolution A=", A); dbg::zout("convolution B=", B); vl C(n); rep(i, n) C[i] = pp(A[i] * B[i]).val; dbg::zout("convolution C=", C); vl c = fft_reverse(C); dbg::zout("convolution c =", c); return c; } }; // namespace zz_poly using namespace zz_poly; ///////////////////////////////////////////////// ll Gn_pre(vxy& vec, const ll mod) { dbg::zout("Gn_pre(", vec, ")"); ll n = vec.size(); rep(i, n) { rep(j, i) { ll d = gcd(vec[i].second, vec[j].second); dbg::zout("Gn_pre: vec=", vec); dbg::zout("Gn_pre: i,j=", xy{i, j}, vec[i], vec[j]); dbg::zout("Gn_pre: d=", d); if ((vec[i].first - vec[j].first) % d != 0) return -1; vec[i].second /= d; vec[j].second /= d; ll di = gcd(vec[i].second, d); ll dj = d / di; do { d = gcd(di, dj); di *= d; dj /= d; } while (d != 1); vec[i].second *= di; vec[j].second *= dj; vec[i].first %= vec[i].second; vec[j].first %= vec[j].second; } } ll lcm_val = 1; each(ite, vec) lcm_val = ((__int128)lcm_val * ite->second) % mod; return lcm_val; } template ll Gn(vxy vec, bool pos = false) { bool zero_possible = true; each(ite, vec) { if (ite->first > 0) { zero_possible = false; break; } } ll pre_ans = Gn_pre(vec, m); if (pre_ans == -1) return -1; if (zero_possible) return pre_ans; dbg::zout("Gn vec=", vec); ll n = vec.size(); ll mod = m; if (n == 0) return -1; if (mod <= 1) { mod = lcm([&vec]() { vl v; each(ite, vec) v.push_back(ite->second); return v; }()); // mod++; } dbg::zout("Gn: mod=", mod, " vec=", vec); vl coef(n + 1, 1), cval(n + 1, 0); vec.emplace_back(0, mod); rep(i, n) { // r1 = r1 + (r2 - r1) * inv(p1%p2) * p1 // p1 = lcm(p1,p2) ll r = vec[i].first, p = vec[i].second; dbg::zout("Gn : i=", i); dbg::zout("Gn : coef=", coef); dbg::zout("Gn : cval=", cval); xy ans = gcdex(coef[i], p); // x * p1 + y * p2 = 1 ll ta = (r - cval[i]) % p; if (ta < 0) ta += p; ll tb = ans.first % p; if (tb < 0) tb += p; ll t = ((__int128)ta * tb) % p; cnt(j, i + 1, n) { cval[j] = (cval[j] + (__int128)t * coef[j]) % vec[j].second; coef[j] = ((__int128)coef[j] * p) % vec[j].second; } } return cval.back(); } int main() { dbg::unprint = true; ll N; cin >> N; vl X(N), Y(N); rep(i, N) cin >> X[i] >> Y[i]; vxy vec; rep(i, N) vec.emplace_back(X[i], Y[i]); cout << Gn<1000000007>(vec, true) << endl; return 0; }