#include using namespace std; #define rep(i, n) for (decltype(n) i = 0; i < (n); ++i) #define rep3(i, s, n) for (decltype(n) i = (s); i < (n); ++i) #define repR(i, n) for (decltype(n) i = (n)-1; i >= 0; --i) #define rep3R(i, s, n) for (decltype(n) i = (n)-1; i >= (s); --i) #define repit(it, c) for (auto it = (c).begin(); it != (c).end(); ++it) #define all(x) ::std::begin(x), ::std::end(x) using ll = long long; template inline bool chmax(T ¤t, const U &test) { if (current < test) { current = test; return true; } return false; } template inline bool chmin(T ¤t, const U &test) { if (current > test) { current = test; return true; } return false; } const int64_t INFL = pow(10, 18); const int INF = 2 * pow(10, 9); const long long MOD = 1000000007; ll gcd(ll a, ll b) { if (b == 0) { return a; } return gcd(b, a % b); } ll ext_Euclid(ll n, ll m, ll &p, ll &q) { if (m == 0) { p = 1; q = 0; return n; } ll d = ext_Euclid(m, n % m, q, p); q -= n / m * p; return d; } ll inv_mod(ll n, ll m) { ll p, q; ext_Euclid(n, m, p, q); return (p + m) % m; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); constexpr char endl = '\n'; /////////////////////////// int n; cin >> n; vector x(n), y(n); rep(i, n) { cin >> x[i] >> y[i]; } // Garner のアルゴリズムを使う為に y 同士を互いに素にする。 rep(i, n - 1) { rep3(j, i + 1, n) { ll g = gcd(y[i], y[j]); if ((x[i] - x[j]) % g != 0) { cout << -1 << endl; return 0; } y[i] /= g, y[j] /= g; ll gi = gcd(y[i], g), gj = g / gi; g = gcd(gi, gj); gi *= g; gj /= g; assert(gcd(gi, gj) == 1); y[i] *= gi, y[j] *= gj; x[i] %= y[i], x[j] %= y[j]; } } ll lcm = 1; rep(i, n) { (lcm *= y[i]) %= MOD; } // Garner のアルゴリズム y.emplace_back(MOD); vector coeffs(n + 1, 1); vector consts(n + 1, 0); rep(i, n) { // coeff * t + const = b ll t = ((x[i] - consts[i]) * inv_mod(coeffs[i], y[i]) + y[i]) % y[i]; rep3(j, i + 1, n + 1) { (consts[j] += t * coeffs[i]) %= y[j]; (coeffs[j] *= y[i]) %= y[j]; } } if (consts[n] == 0) { consts[n] = lcm; } cout << consts[n] << endl; }