Вам задан генератор кортежей чисел \(f^{(k)} = (f_1^{(k)}, f_2^{(k)}, \dots, f_n^{(k)})\), где \(f_i^{(k)} = (a_i \cdot f_i^{(k - 1)} + b_i) \bmod p_i\) и \(f^{(0)} = (x_1, x_2, \dots, x_n)\). Здесь \(x \bmod y\) означает остаток от деления \(x\) на \(y\). Все \(p_i\) — простые числа.
Можно заметить, что при фиксированных наборах \(x_i\), \(y_i\), \(a_i\) начиная с некоторого номера кортежи \(f^{(k)}\) будут повторять кортежи с меньшими номерами. Найдите максимальное количество различных кортежей (из всех \(f^{(k)}\) при \(k \ge 0\)), которые может выдать данный генератор, если \(x_i\), \(a_i\), \(b_i\) — целые числа в диапазоне \([0, p_i - 1]\) и могут быть выбраны произвольно. Так как ответ может быть слишком большим, выведите остаток от его деления на \(10^9 + 7\).
Выходные данные
Выведите единственное число — максимальное количество различных кортежей по модулю \(10^9 + 7\).
Примечание
В первом примере можно выбрать следующие параметры: \(a = [1, 1, 1, 1]\), \(b = [1, 1, 1, 1]\), \(x = [0, 0, 0, 0]\), тогда \(f_i^{(k)} = k \bmod p_i\).
Во втором примере можно выбрать следующие параметры: \(a = [1, 1, 2]\), \(b = [1, 1, 0]\), \(x = [0, 0, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3 5 7
|
210
|
|
2
|
3
5 3 3
|
30
|