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>
using namespace std;
const int MOD = 1e9 + 7;
int p[200003], N, lst[2000003];
bool nprm[2000003], fl[2000003];
map<int, pair<int, int> > mx;
void init() {
  for (int i = 2; i <= 2e6; ++i)
    if (!nprm[i]) {
      lst[i] = i;
      for (int j = i; 1ll * j * i <= 2e6; ++j) {
        nprm[i * j] = 1;
        if (!lst[i * j]) lst[i * j] = i;
      }
    }
}
void add(int p) {
  int pre = 0, cnt = 0;
  while (p != 1) {
    int t = lst[p];
    p /= t;
    if (pre != t) {
      if (mx[pre].first < cnt) mx[pre].second = 0;
      if (mx[pre].first <= cnt) {
        mx[pre].first = cnt;
        ++mx[pre].second;
      }
      cnt = 0;
    }
    pre = t;
    ++cnt;
  }
  if (mx[pre].first < cnt) mx[pre].second = 0;
  if (mx[pre].first <= cnt) {
    mx[pre].first = cnt;
    ++mx[pre].second;
  }
}
bool check(int p) {
  int pre = 0, cnt = 0;
  while (p != 1) {
    int t = lst[p];
    p /= t;
    if (pre != t) {
      if (pre && mx[pre].first == cnt && mx[pre].second == 1) return 0;
      cnt = 0;
    }
    pre = t;
    ++cnt;
  }
  if (pre && mx[pre].first == cnt && mx[pre].second == 1) return 0;
  return 1;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> N;
  init();
  for (int i = 1; i <= N; ++i) cin >> p[i];
  sort(p + 1, p + N + 1, [&](int p, int q) { return p > q; });
  int pos = 1, tms = 1;
  bool flg = 0;
  while (pos <= N) {
    int p1 = pos;
    while (p1 <= N && p[p1] == p[pos]) ++p1;
    add(p[pos]);
    pos = p1;
  }
  pos = 1;
  while (pos <= N) {
    int p1 = pos;
    while (p1 <= N && p[p1] == p[pos]) ++p1;
    if (p1 - pos + check(p[pos]) >= 2) {
      if (p1 - pos == 1) {
        fl[p[pos]] = 1;
        if (mx[p[pos]].first == 1) --mx[p[pos]].second;
      }
      add(p[pos] - 1);
    }
    pos = p1;
  }
  pos = 1;
  while (pos <= N) {
    int p1 = pos;
    while (p1 <= N && p[p1] == p[pos]) ++p1;
    if (p1 - pos + (p1 - pos == 1 ? fl[p[pos]] : check(p[pos])) +
            check(p[pos] - 1) >=
        3)
      flg = 1;
    pos = p1;
  }
  for (auto t : mx)
    while (t.second.first--) tms = 1ll * tms * t.first % MOD;
  cout << (tms + flg) % MOD;
  return 0;
}