← 返回题目列表

Codeforces · 1030/G

G. 线性同余发生器

中文机器翻译题面 查看原题

给你一个元组生成器 $$$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$$$ 为模。

示例

输入 #1

4
2 3 5 7

输出 #1

210

输入 #2

3
5 3 3

输出 #2

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]$$$。