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;
long long modx(long long Base, long long exponent) {
  long long ans = 1;
  if (Base == 1) return Base;
  while (exponent) {
    if (exponent & 1) ans = (ans * Base) % 1000000007LL;
    Base = (Base * Base) % 1000000007LL;
    exponent = exponent >> 1;
  }
  return ans;
}
long long inmodx(long long num) { return (modx(num, 1000000007LL - 2LL)); }
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
  if (a.first.first / 900 < b.first.first / 900) return 1;
  if (a.first.first / 900 > b.first.first / 900) return 0;
  if (a.first.second <= b.first.second) return 1;
  return 0;
}
const int N = (2e6) + 9;
const int M = (N << 2) + 9;
const int LOGN = ((int)log2(N)) + 3;
const int LOGM = ((int)log2(M)) + 3;
const int BUCK = 450;
int cnt[N], smpf[N], val[N], cnt_max[N];
bool new_cnt[N];
vector<pair<int, int> > factors;
void sieve() {
  int i, j;
  for (i = (0); i < (N); i++) smpf[i] = i;
  for (i = (2); i < (N); i++)
    if (smpf[i] == i)
      for (j = i + i; j < N; j += i) smpf[j] = min(smpf[j], i);
  return;
}
bool add_val(int n) {
  bool ans = 0;
  factors.clear();
  factors.push_back(make_pair(smpf[n], smpf[n]));
  n /= smpf[n];
  while (n > 1) {
    if (smpf[n] == factors.back().first)
      factors.back().second *= smpf[n];
    else
      factors.push_back(make_pair(smpf[n], smpf[n]));
    n /= smpf[n];
  }
  for (auto x : factors) {
    if (x.second > val[x.first]) ans = 1;
    val[x.first] = max(val[x.first], x.second);
  }
  return ans;
}
void update_cnt_max(int n) {
  factors.clear();
  factors.push_back(make_pair(smpf[n], smpf[n]));
  n /= smpf[n];
  while (n > 1) {
    if (smpf[n] == factors.back().first)
      factors.back().second *= smpf[n];
    else
      factors.push_back(make_pair(smpf[n], smpf[n]));
    n /= smpf[n];
  }
  for (auto x : factors)
    if (val[x.first] == x.second) cnt_max[x.first]++;
  return;
}
bool check(int n) {
  factors.clear();
  factors.push_back(make_pair(smpf[n], smpf[n]));
  n /= smpf[n];
  while (n > 1) {
    if (smpf[n] == factors.back().first)
      factors.back().second *= smpf[n];
    else
      factors.push_back(make_pair(smpf[n], smpf[n]));
    n /= smpf[n];
  }
  for (auto x : factors)
    if (val[x.first] == x.second && cnt_max[x.first] == 1) return 0;
  return 1;
}
bool check() {
  int i, j;
  for (i = (2); i < (N); i++)
    if (new_cnt[i]) update_cnt_max(i);
  for (i = (2); i < (N); i++)
    if (new_cnt[i] && check(i)) return 1;
  return 0;
}
void solve() {
  sieve();
  int n, i, a;
  bool flag = 0, temp;
  long long ans = 1LL;
  cin >> n;
  for (i = (1); i < (n + 1); i++) {
    cin >> a;
    cnt[a]++;
  }
  for (i = N - 1; i > 2; i--) {
    if (cnt[i] > 2) {
      flag = 1;
      add_val(i);
      add_val(i - 1);
    } else if (cnt[i] == 2) {
      temp = 1;
      temp &= add_val(i);
      temp &= add_val(i - 1);
      if (temp) {
        new_cnt[i] = 1;
        new_cnt[i - 1] = 1;
      } else
        flag = 1;
    } else if (cnt[i] == 1) {
      temp = add_val(i);
      if (!temp) {
        temp = add_val(i - 1);
        if (temp) new_cnt[i - 1] = 1;
      } else
        new_cnt[i] = 1;
      if (!temp) flag = 1;
    }
  }
  if (cnt[2] > 1) {
    flag = 1;
    add_val(2);
  } else if (cnt[2] == 1) {
    temp = add_val(2);
    if (!temp)
      flag = 1;
    else
      new_cnt[2] = 1;
  }
  for (i = (2); i < (N); i++)
    if (val[i] > 0) {
      ans = (ans * 1LL * val[i]) % 1000000007LL;
    }
  if (!flag) flag = check();
  if (flag) ans = (ans + 1LL) % 1000000007LL;
  cout << ans << '\n';
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1, cs;
  cout << fixed << setprecision(6);
  for (cs = (1); cs < (t + 1); cs++) {
    solve();
  }
  return 0;
}