第一个元素 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 的幂。