#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2e5 + 5, lim = 2e6, Mod = 1e9 + 7;
int i, n, a[Nmax], ap[lim + 2], nr[lim + 2];
vector<int> primes;
vector<pair<int, int> > v[lim + 2];
bool used[Nmax];
bool useless(int x) {
  for (auto it : v[x])
    if (ap[it.first] == it.second && nr[it.first] == 1) return 0;
  return 1;
}
void run_primes(int lim) {
  int i, j;
  for (i = 2; i <= lim; ++i) {
    bool ok = 1;
    for (j = 0; ok && j < primes.size() && primes[j] * primes[j] <= i; ++j)
      if (i % primes[j] == 0) ok = 0;
    if (ok) primes.push_back(i);
  }
}
void add(int x) {
  int X = x;
  if (v[X].empty()) {
    int i, cnt;
    for (i = 0; i < primes.size() && primes[i] * primes[i] <= x; ++i)
      if (x % primes[i] == 0) {
        cnt = 1;
        x /= primes[i];
        while (x % primes[i] == 0) ++cnt, x /= primes[i];
        v[X].push_back({primes[i], cnt});
      }
    if (x > 1) v[X].push_back({x, 1});
  }
  for (auto it : v[X])
    if (it.second > ap[it.first])
      nr[it.first] = 1, ap[it.first] = it.second;
    else if (it.second == ap[it.first])
      ++nr[it.first];
}
int main() {
  run_primes(4000);
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  sort(a + 1, a + n + 1);
  for (i = n; i; --i)
    if (ap[a[i]])
      add(a[i] - 1), used[i] = 1;
    else
      ap[a[i]] = 1;
  bool ok = 0;
  for (i = 1; i <= n; ++i)
    if (used[i] && useless(a[i] - 1)) ok = 1;
  long long ans = 1;
  int j;
  for (i = 1; i <= lim; ++i)
    for (j = 0; j < ap[i]; ++j) ans = ans * i % Mod;
  if (ok) ans = (ans + 1) % Mod;
  cout << ans << '\n';
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

You are given a tuple generator f^{(k)} = (f_1^{(k)}, f_2^{(k)}, ..., f_n^{(k)}), where f_i^{(k)} = (a_i ⋅ f_i^{(k - 1)} + b_i) mod p_i and f^{(0)} = (x_1, x_2, ..., x_n). Here x mod 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 ≥ 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 ≤ n ≤ 2 ⋅ 10^5) — the number of elements in the tuple.

The second line contains n space separated prime numbers — the modules p_1, p_2, …, p_n (2 ≤ p_i ≤ 2 ⋅ 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 mod p_i.

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2e5 + 5, lim = 2e6, Mod = 1e9 + 7;
int i, n, a[Nmax], ap[lim + 2], nr[lim + 2];
vector<int> primes;
vector<pair<int, int> > v[lim + 2];
bool used[Nmax];
bool useless(int x) {
  for (auto it : v[x])
    if (ap[it.first] == it.second && nr[it.first] == 1) return 0;
  return 1;
}
void run_primes(int lim) {
  int i, j;
  for (i = 2; i <= lim; ++i) {
    bool ok = 1;
    for (j = 0; ok && j < primes.size() && primes[j] * primes[j] <= i; ++j)
      if (i % primes[j] == 0) ok = 0;
    if (ok) primes.push_back(i);
  }
}
void add(int x) {
  int X = x;
  if (v[X].empty()) {
    int i, cnt;
    for (i = 0; i < primes.size() && primes[i] * primes[i] <= x; ++i)
      if (x % primes[i] == 0) {
        cnt = 1;
        x /= primes[i];
        while (x % primes[i] == 0) ++cnt, x /= primes[i];
        v[X].push_back({primes[i], cnt});
      }
    if (x > 1) v[X].push_back({x, 1});
  }
  for (auto it : v[X])
    if (it.second > ap[it.first])
      nr[it.first] = 1, ap[it.first] = it.second;
    else if (it.second == ap[it.first])
      ++nr[it.first];
}
int main() {
  run_primes(4000);
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  sort(a + 1, a + n + 1);
  for (i = n; i; --i)
    if (ap[a[i]])
      add(a[i] - 1), used[i] = 1;
    else
      ap[a[i]] = 1;
  bool ok = 0;
  for (i = 1; i <= n; ++i)
    if (used[i] && useless(a[i] - 1)) ok = 1;
  long long ans = 1;
  int j;
  for (i = 1; i <= lim; ++i)
    for (j = 0; j < ap[i]; ++j) ans = ans * i % Mod;
  if (ok) ans = (ans + 1) % Mod;
  cout << ans << '\n';
  return 0;
}

```