CF1030G.Linear Congruential Generator

You are given a tuple generator $f^{(k)} = (f_1^{(k)}, f_2^{(k)}, \dots, f_n^{(k)})$, where $f_i^{(k)} = (a_i \cdot f_i^{(k - 1)} + b_i) \bmod p_i$ and $f^{(0)} = (x_1, x_2, \dots, x_n)$. Here $x \bmod y$ denotes the remainder of $x$ when divided by $y$. All $p_i$ are primes.

One can see that with fixed sequences $x_i$, $y_i$, $a_i$ the tuples $f^{(k)}$ starting from some index will repeat tuples with smaller indices. Calculate the maximum number of different tuples (from all $f^{(k)}$ for $k \ge 0$) that can be produced by this generator, if $x_i$, $a_i$, $b_i$ are integers in the range $[0, p_i - 1]$ and can be chosen arbitrary. The answer can be large, so print the remainder it gives when divided by $10^9 + 7$

给定一个元组生成器 $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$、$a_i$、$b_i$，元组序列 $f^{(k)}$ 从某个下标开始将重复之前出现过的元组（即进入循环）。现要求：在 $x_i$、$a_i$、$b_i$ 均可任意选取、且均取自整数区间 $[0, p_i - 1]$ 的前提下，该生成器所能产生的不同元组的最大个数（即对所有 $k \ge 0$ 的 $f^{(k)}$ 中互异元组的总数最大值）。答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in the tuple.

The second line contains $n$ space separated prime numbers — the modules $p_1, p_2, \ldots, p_n$ ($2 \le p_i \le 2 \cdot 10^6$).

第一行包含一个整数 $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$）。

Print one integer — the maximum number of different tuples modulo $10^9 + 7$.

输出一个整数——模 $10^9 + 7$ 意义下不同元组的最大数量。

In the first example we can choose next parameters: $a = [1, 1, 1, 1]$, $b = [1, 1, 1, 1]$, $x = [0, 0, 0, 0]$, then $f_i^{(k)} = k \bmod p_i$.

In the second example we can choose next parameters: $a = [1, 1, 2]$, $b = [1, 1, 0]$, $x = [0, 0, 1]$.

在第一个例子中，我们可以选择以下参数：$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]$。