Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/19/2019 23:01:18 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|