G. Линейный конгруэнтный генератор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан генератор кортежей чисел $$$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$$$.

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

В первой строке находится целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в кортеже.

Во второй строке находятся $$$n$$$ простых целых чисел — соответствующие модули $$$p_1, p_2, \ldots, p_n$$$ ($$$2 \le p_i \le 2 \cdot 10^6$$$).

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

Выведите единственное число — максимальное количество различных кортежей по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
4
2 3 5 7
Выходные данные
210
Входные данные
3
5 3 3
Выходные данные
30
Примечание

В первом примере можно выбрать следующие параметры: $$$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]$$$.