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>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,mmx,avx,tune=native")
using namespace std;
const int MOD = 1000000007;
const int UNDEF = -1;
const int INF = 1 << 30;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
const int MAXN = 2e6 + 4;
const int MAXP = MAXN;
bool sieve_array[MAXP + 1];
int ap[MAXP + 1];
vector<int> gpv;
void sieve() {
  for (int i = 0; i <= MAXP; i++) {
    sieve_array[i] = true;
    ap[i] = 1 << 30;
  }
  sieve_array[0] = false;
  sieve_array[1] = false;
  int lim = (int)(ceil(sqrt(MAXP))) + 2;
  for (int i = 2; i <= lim; i++) {
    if (sieve_array[i]) {
      for (int j = i * i; j <= MAXP; j += i) {
        sieve_array[j] = false;
        ap[j] = i;
      }
    }
  }
  for (int i = 2; i <= MAXP; i++) {
    if (sieve_array[i]) {
      gpv.push_back(i);
      ap[i] = i;
    }
  }
}
pair<int, int> factorize_dest[500];
int factorize_tmp[500];
int factorize(int x) {
  int tsz = 0;
  while (x > 1) {
    int p = ap[x];
    x /= p;
    factorize_tmp[tsz++] = p;
  }
  if (x > 1) factorize_tmp[tsz++] = x;
  sort(factorize_tmp, factorize_tmp + tsz);
  int didx = 0;
  for (int tidx = 0; tidx < tsz; tidx++) {
    int p = factorize_tmp[tidx];
    if (tidx == 0 || p != factorize_tmp[tidx - 1]) {
      factorize_dest[didx++] = make_pair(p, 1);
    } else
      factorize_dest[didx - 1].second++;
  }
  return didx;
}
vector<pair<int, int> > vfactorize(int x) {
  int ox = x;
  int tsz = 0;
  while (x > 1) {
    int p = ap[x];
    x /= p;
    factorize_tmp[tsz++] = p;
  }
  if (x > 1) factorize_tmp[tsz++] = x;
  sort(factorize_tmp, factorize_tmp + tsz);
  vector<pair<int, int> > dest;
  for (int tidx = 0; tidx < tsz; tidx++) {
    int p = factorize_tmp[tidx];
    if (tidx == 0 || p != factorize_tmp[tidx - 1]) {
      dest.push_back(make_pair(p, 1));
    } else
      dest.back().second++;
  }
  int ans = 1;
  for (auto &w : dest) {
    ;
    for (int i = 0; i < w.second; i++) ans *= w.first;
  }
  for (int i = 1; i < dest.size(); i++)
    ;
  ;
  return dest;
}
inline int _norm(int x) {
  if (x < 0) x += MOD;
  return x;
}
template <int MOD>
struct ModInt {
  static const int Mod = MOD;
  unsigned x;
  ModInt() : x(0) {}
  ModInt(signed sig) {
    sig = _norm(sig);
    x = sig;
  }
  ModInt(signed long long sig) {
    sig = _norm(sig);
    x = sig;
  }
  int get() const { return (int)x; }
  ModInt &operator+=(ModInt that) {
    if ((x += that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(ModInt that) {
    if ((x += MOD - that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator*=(ModInt that) {
    x = ((unsigned long long)x * that.x) % MOD;
    return *this;
  }
  ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
  ModInt &operator+=(int that) {
    that = _norm(that);
    if ((x += that) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(int that) {
    that = _norm(that);
    if ((x += MOD - that) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator*=(int that) {
    that = _norm(that);
    x = ((unsigned long long)x * that) % MOD;
    return *this;
  }
  ModInt &operator/=(int that) {
    that = _norm(that);
    return *this *= ModInt(that).inverse();
  }
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
  ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
  ModInt operator+(int that) const { return ModInt(*this) += that; }
  ModInt operator-(int that) const { return ModInt(*this) -= that; }
  ModInt operator*(int that) const { return ModInt(*this) *= that; }
  ModInt operator/(int that) const { return ModInt(*this) /= that; }
  ModInt inverse() const {
    signed a = x, b = MOD, u = 1, v = 0;
    while (b) {
      signed t = a / b;
      a -= t * b;
      std::swap(a, b);
      u -= t * v;
      std::swap(u, v);
    }
    if (u < 0) u += Mod;
    ModInt res;
    res.x = (unsigned)u;
    return res;
  }
  bool operator==(ModInt that) const { return x == that.x; }
  bool operator!=(ModInt that) const { return x != that.x; }
  ModInt operator-() const {
    ModInt t;
    t.x = x == 0 ? 0 : Mod - x;
    return t;
  }
};
template <int MOD>
ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
  ModInt<MOD> r = 1;
  while (k) {
    if (k & 1) r *= a;
    a *= a;
    k >>= 1;
  }
  return r;
}
const int mn = MAXN;
int c[mn];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  sieve();
  int inpn;
  cin >> inpn;
  for (int i = 0; i < inpn; i++) {
    int inp;
    cin >> inp;
    ++c[inp];
  }
  int extra = 0;
  vector<vector<pair<int, int> > > a;
  map<int, int> hi;
  for (int inp = mn - 1; inp >= 0; inp--) {
    if (c[inp] == 0) continue;
    if (hi[inp] == 0) {
      if (c[inp] > 0) {
        a.push_back(vfactorize(inp));
        for (auto &w : a.back()) chkmax(hi[w.first], w.second);
      }
      if (c[inp] > 1) {
        a.push_back(vfactorize(inp - 1));
        for (auto &w : a.back()) chkmax(hi[w.first], w.second);
      }
      if (c[inp] > 2) extra = 1;
    } else {
      if (c[inp] > 0) {
        a.push_back(vfactorize(inp - 1));
        for (auto &w : a.back()) chkmax(hi[w.first], w.second);
      }
      if (c[inp] > 1) extra = 1;
    }
  }
  map<int, int> sel;
  for (auto &v : a) {
    for (auto &w : v) {
      if (w.second == hi[w.first]) {
        ++sel[w.first];
      }
    }
  }
  for (auto &v : a) {
    bool critical = false;
    for (auto &w : v) {
      if (w.second == hi[w.first] && sel[w.first] == 1) {
        critical = true;
      }
    }
    if (!critical) extra = 1;
  }
  int ans = 1;
  for (auto &w : hi) {
    for (int i = 0; i < w.second; i++) ans = (ans * (long long)w.first) % MOD;
  }
  if (extra > 0) ans++;
  ans %= MOD;
  printf("%d\n", ans);
}