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 MAXN = 2e5 + 10, MAXP = 2e6, MOD = 1e9 + 7;
int n, p[MAXN], fac[MAXP + 1], fp[MAXP + 1], pri[MAXP + 1], n_pri, cp[MAXP + 1],
    cc[MAXP + 1];
bool as_p[MAXN], extra;
long long ans = 1;
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  for (int i = 2; i <= MAXP; i++) {
    if (!fac[i]) fac[i] = pri[++n_pri] = i, fp[i] = 1;
    for (int j = 1; j <= n_pri && pri[j] * i <= MAXP && pri[j] <= fac[i]; j++)
      fac[pri[j] * i] = pri[j],
                   fp[pri[j] * i] = pri[j] == fac[i] ? fp[i] + 1 : 1;
  }
}
void solve() {
  sort(p + 1, p + n + 1, greater<int>());
  for (int i = 1; i <= n; i++) {
    int x = p[i];
    if (!cp[x])
      as_p[i] = true, cp[x] = cc[x] = 1;
    else {
      as_p[i] = false;
      for (x--; x != 1;) {
        int cnt = fp[x];
        if (cnt > cp[fac[x]])
          cp[fac[x]] = cnt, cc[fac[x]] = 1;
        else if (cnt == cp[fac[x]])
          cc[fac[x]]++;
        for (int j = 1; j <= cnt; j++) x /= fac[x];
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    int x = as_p[i] ? p[i] : p[i] - 1;
    bool flg = true;
    for (; x != 1;) {
      int cnt = fp[x];
      if (cnt == cp[fac[x]] && cc[fac[x]] == 1) flg = false;
      for (int j = 1; j <= cnt; j++) x /= fac[x];
    }
    extra |= flg;
  }
  for (int i = 1; i <= MAXP; i++)
    if (fac[i] == i)
      for (int j = 1; j <= cp[i]; j++) (ans *= i) %= MOD;
  (ans += extra ? 1 : 0) %= MOD;
  printf("%lld\n", ans);
}
int main() {
  init();
  solve();
}