Geometric Progressions

- 给定 $n$ 以及 $n$ 个正整数对 $a_i, b_i$。 - 第 $i$ 对 $a_i, b_i$ 确定了一个序列 $\{a_i, a_i b_i, a_i b_i^2, a_i b_i^3, \ldots \}$。 - 询问最小的在 $n$ 个序列中都有出现的数，或者判断不存在。 - $n \le 100$，$a_i, b_i \le {10}^9$，答案对 ${10}^9 + 7$ 取模。

Geometric progression with the first element $ a $ and common ratio $ b $ is a sequence of numbers $ a,ab,ab^{2},ab^{3},... $ . You are given $ n $ integer geometric progressions. Your task is to find the smallest integer $ x $ , that is the element of all the given progressions, or else state that such integer does not exist.

The first line contains integer ( $ 1<=n<=100 $ ) — the number of geometric progressions. Next $ n $ lines contain pairs of integers $ a,b $ ( $ 1<=a,b<=10^{9} $ ), that are the first element and the common ratio of the corresponding geometric progression.

If the intersection of all progressions is empty, then print $ -1 $ , otherwise print the remainder of the minimal positive integer number belonging to all progressions modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).

2
2 2
4 1

4

2
2 2
3 3

-1

In the second sample test one of the progressions contains only powers of two, the other one contains only powers of three.