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;
namespace Base {
const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
const long long infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
template <typename T>
void read(T &x) {
  x = 0;
  int fh = 1;
  double num = 1.0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') fh = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  if (ch == '.') {
    ch = getchar();
    while (isdigit(ch)) {
      num /= 10;
      x = x + num * (ch - '0');
      ch = getchar();
    }
  }
  x = x * fh;
}
template <typename T>
void chmax(T &x, T y) {
  x = x < y ? y : x;
}
template <typename T>
void chmin(T &x, T y) {
  x = x > y ? y : x;
}
}  // namespace Base
using namespace Base;
const int N = 200010, L = 2000000, M = 2000010, P = 1e9 + 7;
int n, a[N], cnt[M], p[M], hav[M], use[M], pnum, g[M];
int power(int x, int y) {
  int i = x;
  x = 1;
  while (y > 0) {
    if (y % 2 == 1) x = 1ll * x * i;
    i = 1ll * i * i;
    y /= 2;
  }
  return x;
}
long long ans = 1;
int ins(int x) {
  int num = 1;
  for (int i = 1; p[i] * p[i] <= x; i++)
    if (x % p[i] == 0) {
      int cnt = 0;
      while (x % p[i] == 0) cnt++, x /= p[i];
      if (cnt > hav[p[i]]) num = num * power(p[i], cnt - hav[p[i]]);
    }
  if (x != 1)
    if (hav[x] == 0) num = num * x;
  return num;
}
void join(int x) {
  int num = 1;
  for (int i = 1; p[i] * p[i] <= x; i++)
    if (x % p[i] == 0) {
      int cnt = 0;
      while (x % p[i] == 0) cnt++, x /= p[i];
      if (cnt > hav[p[i]])
        num = num * power(p[i], cnt - hav[p[i]]), hav[p[i]] = cnt, g[p[i]] = 0;
      if (cnt == hav[p[i]]) g[p[i]]++;
    }
  if (x != 1) {
    if (hav[x] == 0) num = num * x, hav[x] = 1, g[x] = 0;
    if (hav[x] == 1) g[x]++;
  }
  ans = ans * num % P;
}
void liner(int n) {
  use[1] = true;
  for (int i = 2; i <= n; i++) {
    if (use[i] == false) p[++pnum] = i;
    for (int j = 1; 1ll * p[j] * i <= n; j++) {
      use[i * p[j]] = true;
      if (i % p[j] == 0) break;
    }
  }
}
bool delt(int x) {
  int num = 0;
  for (int i = 1; p[i] * p[i] <= x; i++)
    if (x % p[i] == 0) {
      int cnt = 0;
      while (x % p[i] == 0) cnt++, x /= p[i];
      if (cnt == hav[p[i]] && g[p[i]] == 1) num = 1;
    }
  if (x != 1)
    if (hav[x] == 1 && g[x] == 1) num = 1;
  return num;
}
int main() {
  read(n);
  for (int i = 1; i <= n; i++) read(a[i]);
  sort(a + 1, a + n + 1);
  liner(L);
  bool flag = false;
  for (int i = n; i >= 1; i--) {
    int las = ans;
    if (ins(a[i]) >= ins(a[i] - 1))
      join(a[i]);
    else
      join(a[i] - 1);
    if (las == ans) flag = true;
  }
  for (int i = n; i >= 1; i--)
    if (delt(a[i]) + delt(a[i] - 1) == 0 ||
        (a[i] == a[i + 1] && delt(a[i] - 1) == 0)) {
      flag = true;
    }
  ans = (ans + flag) % P;
  printf("%lld\n", ans);
  return 0;
}