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 = 2e6 + 5;
const int MOD = 1e9 + 7;
int opt, ans = 1, low[MAXN], vis[MAXN], mx[MAXN], cnt[MAXN], dat[MAXN];
inline int read() {
  int x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
template <typename T1, typename T2>
inline void Max(T1 &x, T2 y) {
  if (x < y) x = y;
}
inline int qpow(int x, int y) {
  long long r = 1, k = x;
  while (y) {
    if (y & 1) r *= k, r %= MOD;
    k *= k, k %= MOD, y >>= 1;
  }
  return r;
}
inline void update(int p, int x) {
  if (x > mx[p])
    mx[p] = x, cnt[p] = 1;
  else if (x == mx[p])
    cnt[p]++;
}
inline int check(int x) {
  while (x != 1) {
    int p = low[x], c = 0;
    while (x % p == 0) x /= p, c++;
    if (c == mx[p] && cnt[p] == 1) return 0;
  }
  return 1;
}
int main() {
  int n = read(), m = 0;
  for (int i = 1; i <= n; i++) Max(m, dat[i] = read());
  sort(dat + 1, dat + n + 1);
  for (int i = 2; i <= m; i++)
    if (!low[i])
      for (int j = i; j <= m; j += i)
        if (!low[j]) low[j] = i;
  for (int i = n; i; i--) {
    int v = dat[i];
    if (!mx[v])
      update(v, 1), ans = 1ll * ans * v % MOD;
    else {
      vis[i] = 1, v--;
      while (v != 1) {
        int p = low[v], c = 0;
        while (v % p == 0) v /= p, c++;
        if (c > mx[p]) {
          ans = 1ll * ans * qpow(p, c - mx[p]) % MOD;
          mx[p] = c, cnt[p] = 1;
        } else if (c == mx[p])
          cnt[p]++;
      }
    }
  }
  for (int i = 1; i <= n; i++) opt |= (vis[i] && check(dat[i] - 1));
  printf("%d\n", ans + opt);
  return 0;
}