Геометрической прогрессией с первым элементом a и знаменателем b называется последовательность чисел a, ab, ab2, ab3, ....
Задано n целочисленных геометрических прогрессий. Требуется найти наименьшее целое число x, которое является элементом всех заданных прогрессий, либо сообщить, что такого не существует.
Выходные данные
Если пересечение всех прогрессий пусто, то выведите - 1, иначе выведите остаток от деления минимального числа, принадлежащего всем прогрессиями, на 1000000007 (109 + 7).
Примечание
Во втором тестовом примере одна из прогрессий содержит только степени двойки, другая — только степени тройки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 2
4 1
|
4
|
|
2
|
2
2 2
3 3
|
-1
|