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 int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline unsigned long long icbrt(unsigned long long k) {
  unsigned long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
const int maxn = 2e6 + 5;
int sp[maxn];
int n;
int p[maxn];
vector<int> cnt[maxn];
int g[maxn];
void volamtruyenkyii() {
  for (int i = (1); i < (maxn); ++i) sp[i] = i;
  for (int i = (2); i < (maxn); ++i)
    if (sp[i] == i) {
      for (int j = i; j < maxn; j += i) {
        chkmin(sp[j], i);
      }
    }
  cin >> n;
  map<int, int> hs;
  for (int i = (0); i < (n); ++i) cin >> p[i], hs[-p[i]]++;
  for (auto it : hs) {
    int p = -it.first;
    if (!int((cnt[p]).size())) {
      cnt[p].push_back(1);
    } else {
      g[p] = 1;
      int t = p - 1;
      map<int, int> f;
      while (t > 1) {
        f[sp[t]]++;
        t /= sp[t];
      }
      for (auto it : f) {
        cnt[it.first].push_back(it.second);
      }
    }
    if (it.second > 1) {
      int t = p - 1;
      map<int, int> f;
      while (t > 1) {
        f[sp[t]]++;
        t /= sp[t];
      }
      for (auto it : f) {
        cnt[it.first].push_back(it.second);
      }
    }
  }
  for (int i = (2); i < (maxn); ++i) cnt[i].push_back(0);
  for (int i = (2); i < (maxn); ++i) sort((cnt[i]).begin(), (cnt[i]).end());
  int add = 0;
  for (auto it : hs)
    if (!add) {
      int p = -it.first;
      if (g[p] || it.second > 1) {
        int t = p - 1;
        map<int, int> f;
        while (t > 1) {
          f[sp[t]]++;
          t /= sp[t];
        }
        int ok = 1;
        for (auto it : f) {
          if (lower_bound((cnt[it.first]).begin(), (cnt[it.first]).end(),
                          it.second) -
                  cnt[it.first].begin() ==
              int((cnt[it.first]).size()) - 1) {
            ok = 0;
            break;
          }
        }
        if (ok) {
          add = 1;
        }
      }
      if (it.second > 2) {
        add = 1;
      }
    }
  int res = 1;
  for (int i = (2); i < (maxn); ++i) res = mult(res, fpow(i, cnt[i].back()));
  addmod(res, add);
  cout << res << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  volamtruyenkyii();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}