← 返回题目列表

Codeforces · 571/E

E. 几何级数

中文机器翻译题面 查看原题

第一个元素 a 和公比 b 的几何级数是数字 a、ab、ab2、ab3、... 的序列。

给你 n 个整数等比级数。您的任务是找到最小的整数 x,即所有给定级数的元素,否则说明该整数不存在。

输入

第一行包含整数 (1 ≤ n ≤ 100) — 等比级数的数量。

接下来的 n 行包含整数对 a、b (1 ≤ a, b ≤ 109),它们是第一个元素和相应等比级数的公比。

输出

如果所有级数的交集为空,则打印 - 1,否则打印属于所有级数的最小正整数模 1000000007 (109 + 7) 的余数。

示例

输入 #1

2
2 2
4 1

输出 #1

4

输入 #2

2
2 2
3 3

输出 #2

-1

注意

在第二个样本测试中,一个级数仅包含 2 的幂,另一个级数仅包含 3 的幂。