Технокубок 2019 - Отборочный Раунд 1 |
---|
Закончено |
Вам задан генератор кортежей чисел $$$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]$$$.
Название |
---|