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>
template <typename Y>
inline bool updmin(Y &a, Y b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename Y>
inline bool updmax(Y &a, Y b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename Y>
inline Y abs(Y a) {
  if (a < 0) a = -a;
  return a;
}
template <typename Y>
inline Y sqr(Y a) {
  return a * a;
}
int read() {
  int w = 1, q = 0, ch = ' ';
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') w = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) q = q * 10 + ch - 48;
  return q * w;
}
inline void FileIO() {
  freopen(
      ""
      ".in",
      "r", stdin);
  freopen(
      ""
      ".out",
      "w", stdout);
}
std::vector<int> s;
const int N = 2000010, M = 2000001, mod = 1000000007;
int n, pri[N], isp[N], pc = 0, low[N], a[N];
int use[N], mxp[N], mtp[N];
inline int qpow(int b, int p) {
  int r = 1;
  for (; p; p >>= 1) {
    if (p & 1) r = (long long)r * b % mod;
    b = (long long)b * b % mod;
  }
  return r;
}
inline void Insert(int x) {
  s.push_back(x);
  while (x > 1) {
    int y = low[x], c = 0;
    for (; low[x] == y; x /= low[x]) c++;
    if (use[y]) {
      use[y] = 0;
      Insert(y - 1);
    }
    if (mxp[y] == c) {
      mtp[y] = 1;
    } else if (updmax(mxp[y], c)) {
      mtp[y] = 0;
    }
  }
}
int main() {
  memset(isp, 1, sizeof isp);
  isp[1] = 0;
  for (int i = 2; i <= M; i++) {
    if (isp[i]) {
      pri[++pc] = i;
      low[i] = i;
    }
    for (int j = 1; j <= pc && i * pri[j] <= M; j++) {
      isp[i * pri[j]] = 0;
      low[i * pri[j]] = pri[j];
      if (!(i % pri[j])) {
        break;
      }
    }
  }
  n = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
  }
  std::sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; i++) {
    if (!use[a[i]]) {
      use[a[i]] = 1;
    } else {
      Insert(a[i] - 1);
    }
  }
  int pp = 0;
  for (auto x : s) {
    while (x > 1) {
      int y = low[x], c = 0;
      for (; low[x] == y; x /= low[x]) c++;
      if (c == mxp[y] && !mtp[y]) {
        x = 0;
        break;
      }
    }
    pp |= x == 1;
  }
  int ans = 1;
  for (int i = 1; i <= pc; i++) {
    if (use[pri[i]]) {
      ans = (long long)ans * pri[i] % mod;
    } else if (mxp[pri[i]]) {
      ans = (long long)ans * qpow(pri[i], mxp[pri[i]]) % mod;
    }
  }
  ans = (ans + pp) % mod;
  printf("%d\n", ans);
  return 0;
}