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.

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$).

Note

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