def extgcd(a, b) if b.zero? {x: 1, y: 0, gcd: a} else prev = extgcd(b, a % b) { x: prev[:y], y: prev[:x] - (a / b) * prev[:y], gcd: prev[:gcd] } end end def mod_inv(a,m) res = extgcd(a,m) x = res[:x] (m + x%m) % m end def lc(as,bs,ms) x,m = 0,1 as.size.times do |i| a = as[i]*m b = bs[i] - as[i]*x d = ms[i].gcd(a) return if b%d != 0 t = b/d * mod_inv(a/d, ms[i]/d) % (ms[i]/d) x = x + m*t m *= ms[i]/d end return [x%m, m] end n = gets.to_i t = [] n.times do x,y = gets.chomp.split.map(&:to_i) t << [x,y] end xs,ys = t.transpose as = [1] * n ans = lc(as,xs,ys) puts -> (x){ if x.nil? -1 else x[0] == 0 ? x[0] : x[0] % 1000000007 end }.call(ans)