Problem: 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].

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const int md = 1e9 + 7;
const long long inf = 4e18;
const int OO = 1;
const int OOO = 1;
using namespace std;
const int M = 2e6 + 10;
int n;
vector<int> a;
vector<int> useful;
map<int, int> have;
long long ans = 1;
int sieve[M], cnt[M];
vector<pair<int, int>> ind[M];
void preprocess() {
  int i = 2;
  for (; i * i <= M; i++) {
    if (!sieve[i]) {
      sieve[i] = i;
      for (int j = i * i; j < M; j += i)
        if (!sieve[j]) sieve[j] = i;
    }
  }
  for (; i < M; i++)
    if (!sieve[i]) sieve[i] = i;
}
void work(int val, int i) {
  if (val == 1) return;
  int p = sieve[val], c = 0;
  while (val % p == 0) {
    c++;
    val /= p;
  }
  ind[p].emplace_back(c, i);
  while (cnt[p] < c) {
    cnt[p]++;
    ans = (ans * p) % md;
  }
  work(val, i);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  preprocess();
  cin >> n;
  a.resize(n);
  useful.resize(n, 0);
  for (auto &i : a) cin >> i;
  sort(a.rbegin(), a.rend());
  for (int i = 0; i < n; i++) {
    int x = a[i];
    if (have[x] >= 2) continue;
    long long cur = ans;
    work(x - have[x], i);
    have[x]++;
    if (have[x] == 1 && cur == ans) {
      ind[x].pop_back();
      work(x - 1, i);
      have[x]++;
    }
  }
  for (int i = 2; i < M; i++) {
    if (ind[i].size() == 0) continue;
    auto mx = *max_element(ind[i].begin(), ind[i].end());
    bool found = false;
    for (const auto &j : ind[i])
      if (mx.first == j.first && mx.second != j.second) found = true;
    if (!found) useful[mx.second] = 1;
  }
  if (*min_element(useful.begin(), useful.end()) == 0) ans = (ans + 1) % md;
  return cout << ans << endl, 0;
}