Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Linear Congruential Generator

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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$$$

Input

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$$$).

Output

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

Examples

Input

4

2 3 5 7

Output

210

Input

3

5 3 3

Output

30

Note

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/19/2018 07:27:45 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|