#P1030G. Linear Congruential Generator

Linear Congruential Generator

Description

You are given a tuple generator f(k)=(f1(k),f2(k),,fn(k))f^{(k)} = (f_1^{(k)}, f_2^{(k)}, \dots, f_n^{(k)}), where fi(k)=(aifi(k1)+bi)modpif_i^{(k)} = (a_i \cdot f_i^{(k - 1)} + b_i) \bmod p_i and f(0)=(x1,x2,,xn)f^{(0)} = (x_1, x_2, \dots, x_n). Here xmodyx \bmod y denotes the remainder of xx when divided by yy. All pip_i are primes.

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

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

The second line contains nn space separated prime numbers — the modules p1,p2,,pnp_1, p_2, \ldots, p_n (2pi21062 \le p_i \le 2 \cdot 10^6).

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

Input

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

The second line contains nn space separated prime numbers — the modules p1,p2,,pnp_1, p_2, \ldots, p_n (2pi21062 \le p_i \le 2 \cdot 10^6).

Output

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

Samples

样例输入 1

4
2 3 5 7

样例输出 1

210

样例输入 2

3
5 3 3

样例输出 2

30

Note

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

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