E. Геометрические прогрессии
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Геометрической прогрессией с первым элементом a и знаменателем b называется последовательность чисел a, ab, ab2, ab3, ....

Задано n целочисленных геометрических прогрессий. Требуется найти наименьшее целое число x, которое является элементом всех заданных прогрессий, либо сообщить, что такого не существует.

Входные данные

В первой строке задано целое число (1 ≤ n ≤ 100) — количество геометрических прогрессий.

В следующих n строках заданы пары целых числа a, b (1 ≤ a, b ≤ 109), являющиеся первым элементом и знаменателем соответствующей геометрической прогрессии.

Выходные данные

Если пересечение всех прогрессий пусто, то выведите  - 1, иначе выведите остаток от деления минимального числа, принадлежащего всем прогрессиями, на 1000000007 (109 + 7).

Примеры
Входные данные
2
2 2
4 1
Выходные данные
4
Входные данные
2
2 2
3 3
Выходные данные
-1
Примечание

Во втором тестовом примере одна из прогрессий содержит только степени двойки, другая — только степени тройки.