Geometric Progressions

Description:

Input:

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⁹), that are the first element and the common ratio of the corresponding geometric progression.

Output:

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⁹ + 7).

Sample Input:

2
2 2
4 1

Sample Output:

4

Sample Input:

2
2 2
3 3

Sample Output:

-1

Note:

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