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;
template <typename T>
bool chkmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <typename T>
bool chkmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
int readint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int cys = 1000000007;
int n, tot;
long long a[200005], p[2000005], cnt[2000005], prm[10005];
bool fl[10005];
vector<pair<int, int> > v[200005];
long long qpow(long long x, long long p) {
  long long ret = 1;
  for (; p; p >>= 1, x = x * x % cys)
    if (p & 1) ret = ret * x % cys;
  return ret;
}
void getprime(int N) {
  fl[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (!fl[i]) prm[++tot] = i;
    for (int j = 1; j <= tot && i * prm[j] <= N; j++) {
      fl[i * prm[j]] = 1;
      if (i % prm[j] == 0) break;
    }
  }
}
int main() {
  getprime(10000);
  n = readint();
  for (int i = 1; i <= n; i++) a[i] = readint();
  sort(a + 1, a + n + 1);
  reverse(a + 1, a + n + 1);
  long long ans = 1;
  for (int i = 1; i <= n; i++) {
    if (!p[a[i]])
      v[i].push_back(make_pair(a[i], 1)), p[a[i]] = 1;
    else {
      int tmp = a[i] - 1;
      for (int j = 1; j <= tot && prm[j] <= sqrt(tmp); j++) {
        if (tmp % prm[j] == 0) {
          long long cnt = 0;
          while (tmp % prm[j] == 0) cnt++, tmp /= prm[j];
          chkmax(p[prm[j]], cnt);
          v[i].push_back(make_pair(prm[j], cnt));
        }
      }
      if (tmp > 1) {
        chkmax(p[tmp], 1ll);
        v[i].push_back(make_pair(tmp, 1));
      }
    }
  }
  for (int i = 1; i <= n; i++)
    for (auto r : v[i])
      if (r.second == p[r.first]) cnt[r.first]++;
  bool ff = 0;
  for (int i = 1; i <= n; i++) {
    bool can = 1;
    for (auto r : v[i])
      if (r.second == p[r.first] && cnt[r.first] == 1) can = 0;
    if (can) {
      ff = 1;
      break;
    }
  }
  for (int i = 1; i <= 2000000; i++) ans = ans * qpow(i, p[i]) % cys;
  printf("%lld\n", (ans + ff) % cys);
  return 0;
}