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 long long inf = 2147383647;
const double pi = 2 * acos(0.0);
const double eps = 1e-9;
using ll = long long;
template <typename S, typename T>
void xmin(S &a, T const &b) {
  if (b < a) a = b;
}
template <typename S, typename T>
void xmax(S &a, T const &b) {
  if (b > a) a = b;
}
struct debugger {
  template <typename T>
  debugger &operator,(const T &v) {
    cerr << v << " ";
    return *this;
  }
} dbg;
inline long long gcd(long long a, long long b) {
  a = ((a) < 0 ? -(a) : (a));
  b = ((b) < 0 ? -(b) : (b));
  while (b) {
    a = a % b;
    swap(a, b);
  }
  return a;
}
long long ext_gcd(long long A, long long B, long long *X, long long *Y) {
  long long x2, y2, x1, y1, x, y, r2, r1, q, r;
  x2 = 1;
  y2 = 0;
  x1 = 0;
  y1 = 1;
  for (r2 = A, r1 = B; r1 != 0;
       r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y) {
    q = r2 / r1;
    r = r2 % r1;
    x = x2 - (q * x1);
    y = y2 - (q * y1);
  }
  *X = x2;
  *Y = y2;
  return r2;
}
inline long long modInv(long long a, long long m) {
  long long x, y;
  ext_gcd(a, m, &x, &y);
  x %= m;
  if (x < 0) x += m;
  return x;
}
inline long long power(long long a, long long p) {
  long long res = 1, x = a;
  while (p) {
    if (p & 1) res = (res * x);
    x = (x * x);
    p >>= 1;
  }
  return res;
}
inline long long bigmod(long long a, long long p, long long m) {
  long long res = 1 % m, x = a % m;
  while (p) {
    if (p & 1) res = (res * x) % m;
    x = (x * x) % m;
    p >>= 1;
  }
  return res;
}
signed gen(int T) {
  mt19937 rng(43151);
  auto get_rand = [&](int64_t l, int64_t r) {
    return uniform_int_distribution<int64_t>(l, r)(rng);
  };
  auto get_double = [&](double l, double r) {
    return uniform_real_distribution<double>(l, r)(rng);
  };
  ofstream o("gen.txt");
  o << T << "\n";
  for (int cas = 0; cas < T; ++cas) {
    o << "\n";
  }
  o << endl;
  o.close();
  return 0;
}
const int N = 2000000;
vector<int> sieve(N + 1);
void init() {
  iota(sieve.begin(), sieve.end(), 0);
  for (int i = 2; i * i <= N; i++) {
    if (sieve[i] == i) {
      for (int j = i * i; j <= N; j += i) {
        xmin(sieve[j], i);
      }
    }
  }
}
vector<pair<int, int>> factorize(int n) {
  vector<pair<int, int>> res;
  while (n > 1) {
    int p = sieve[n];
    res.push_back({p, 0});
    while (n % p == 0) {
      res.back().second++;
      n /= p;
    }
  }
  return move(res);
}
const int mod = 1000000007;
signed main() {
  init();
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> P(n);
  for (int &p : P) {
    cin >> p;
  }
  sort(P.rbegin(), P.rend());
  unordered_map<int, int> exps, freqs;
  vector<vector<pair<int, int>>> facs(n);
  vector<bool> used(n);
  for (long long i = (0); i <= (n - 1); ++i) {
    facs[i] = factorize(P[i] - 1);
    if (exps[P[i]] == 0) {
      exps[P[i]] = 1;
      freqs[P[i]] = 1;
      used[i] = true;
      continue;
    }
    for (auto it : facs[i]) {
      int p = it.first, q = it.second;
      if (q > exps[p]) {
        exps[p] = q;
        freqs[p] = 1;
      } else if (q == exps[p]) {
        freqs[p]++;
      }
    }
  }
  long long res = 1;
  for (auto it : exps) {
    int p = it.first, q = it.second;
    for (long long i = (1); i <= (q); ++i) {
      res = (((res) * (p)) % mod);
    }
  }
  bool flag = false;
  for (long long i = (0); i <= (n - 1); ++i) {
    bool valid = true;
    if (used[i]) {
      if (exps[P[i]] == 1 and freqs[P[i]] == 1) {
        valid = false;
      }
    } else {
      for (auto it : facs[i]) {
        int p = it.first, q = it.second;
        if (q == exps[p] and freqs[p] == 1) {
          valid = false;
        }
      }
    }
    if (valid) {
      flag = true;
    }
  }
  if (flag) {
    res++;
    if (res >= mod) res -= mod;
    ;
  }
  cout << res << endl;
  return 0;
}