No tag edit access

E. Geometric Progressions

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGeometric 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.

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^{9}), 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^{9} + 7).

Examples

Input

2

2 2

4 1

Output

4

Input

2

2 2

3 3

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.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2017 23:40:07 (c6).

Desktop version, switch to mobile version.

User lists

Name |
---|