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>
inline int readChar();
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size = 4096;
inline int getChar() {
  static char buf[buf_size];
  static int len = 0, pos = 0;
  if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
  if (pos == len) return -1;
  return buf[pos++];
}
inline int readChar() {
  int c = getChar();
  while (c <= 32) c = getChar();
  return c;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T x = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return s == 1 ? x : -x;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
  if (write_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end) {
  if (x < 0) writeChar('-'), x = -x;
  char s[24];
  int n = 0;
  while (x || !n) s[n++] = '0' + x % 10, x /= 10;
  while (n--) writeChar(s[n]);
  if (end) writeChar(end);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
struct Flusher {
  ~Flusher() {
    if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  }
} flusher;
inline void readWord(char *s) {
  int c = readChar();
  while (c > 32) *s++ = c, c = getChar();
  *s = 0;
}
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using ull = unsigned long long;
const int maxn = 2e6;
const int mod = 998244353;
const int M = 1e9 + 7;
const int inf = 1e4;
const ll inf64 = 3e18L;
const ld pi = acos((ld)-1.0);
const ld eps = (ld)1e-6;
const int di[] = {0, 0, 1, -1, 0};
const int dj[] = {1, -1, 0, 0, 0};
const int SQ = 1000;
vi lp(maxn + 1);
vector<bool> on(maxn + 1, false);
vi hi(maxn + 1, 0);
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  iota(begin(lp), end(lp), 0);
  for (int i = 2; i * i <= maxn; i++)
    if (lp[i] == i)
      for (int j = i * i; j <= maxn; j += i)
        if (i < lp[j]) lp[j] = i;
  int n;
  cin >> n;
  vi a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  sort(begin(a), end(a));
  for (int i = n - 1; i >= 0; i--)
    if (on[a[i]]) {
      int first = --a[i];
      while (first != 1) on[lp[first]] = true, first /= lp[first];
    } else
      on[a[i]] = true;
  bool flag = false;
  for (int first : a) {
    bool bad = true;
    while (first != 1) {
      int pr = lp[first], pw = 0;
      while (first % pr == 0) first /= pr, pw++;
      if (pw > hi[pr]) bad = false, hi[pr] = pw;
    }
    if (bad) flag = true;
  }
  ll ans = 1;
  for (int i = 2; i <= maxn; i++)
    while (hi[i]--) ans = (ans * i) % M;
  cout << (ans + flag) % M;
}