CF1030G Linear Congruential Generator

给定一个元组生成器 $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)}$ 会重复出现之前的元组。请计算该生成器在 $x_i$、$a_i$、$b_i$ 可以在区间 $[0, p_i - 1]$ 内任意选择的情况下，最多能生成多少个不同的元组（即所有 $k \ge 0$ 的 $f^{(k)}$ 的不同取值个数）。答案可能很大，请输出其对 $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$ 取余的结果。

在第一个样例中，可以选择如下参数：$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]$。 由 ChatGPT 4.1 翻译