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