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("O3")
using namespace std;
template <class c>
struct rge {
  c h, n;
};
template <class c>
rge<c> range(c h, c n) {
  return rge<c>{h, n};
}
template <class c, class F>
struct rgm {
  c h, n;
  F f;
};
template <class c, class F>
rgm<c, F> map_range(c b, c e, F f) {
  return rgm<c, F>{b, e, f};
}
template <class c, class F>
rgm<typename c::const_iterator, F> map_range(const c &x, F f) {
  return map_range(x.begin(), x.end(), f);
}
template <class c>
auto dud(c *r) -> decltype(cerr << *r);
template <class c>
char dud(...);
struct muu {
  template <class c>
  muu &operator<<(const c &) {
    return *this;
  }
  muu &operator()() { return *this; }
};
const int nax = 2e6 + 44, mod = 1e9 + 7;
int __div__ejJ46[nax];
pair<int, int> __exP__QkL47[nax];
int primes[nax];
void add(int p, int e) {
  if (__exP__QkL47[p].first < e)
    __exP__QkL47[p] = make_pair(e, 1);
  else if (__exP__QkL47[p].first == e)
    __exP__QkL47[p].second++;
}
int main() {
  for (int p = 2; p < nax; ++p)
    if (__div__ejJ46[p] == 0)
      for (int k = p; k < nax; k += p) __div__ejJ46[k] = p;
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", primes + i);
  sort(primes, primes + n, greater<int>());
  vector<int> used;
  for (int i = 0; i < n; ++i) {
    (muu() << __FUNCTION__ << "#" << 81 << ": ") << "["
                                                    "primes"
                                                    "["
                                                    "i"
                                                    ": "
                                                 << (i)
                                                 << "] "
                                                    ": "
                                                 << primes[i] << "] ";
    if (__exP__QkL47[primes[i]].first == 0) {
      used.push_back(primes[i]);
      add(primes[i], 1);
    } else {
      int fac = primes[i] - 1;
      used.push_back(fac);
      while (fac > 1) {
        int p = __div__ejJ46[fac];
        int e = 0;
        while (fac % p == 0) {
          fac /= p;
          e++;
        }
        add(p, e);
      }
    }
  }
  (muu() << __FUNCTION__ << "#" << 99 << ": ") << "["
                                                  "used"
                                                  ": "
                                               << (used) << "] ";
  bool add = false;
  for (int x : used) {
    bool full = true;
    int xx = x;
    while (xx > 1) {
      int p = __div__ejJ46[xx];
      int e = 0;
      while (xx % p == 0) {
        xx /= p;
        e++;
      }
      if (__exP__QkL47[p].first == e && __exP__QkL47[p].second < 2) {
        (muu() << __FUNCTION__ << "#" << 112 << ": ") << "["
                                                         "x"
                                                         ": "
                                                      << (x)
                                                      << "] "
                                                         " failed on "
                                                         "["
                                                         "exp"
                                                         "["
                                                         "p"
                                                         ": "
                                                      << (p)
                                                      << "] "
                                                         ": "
                                                      << __exP__QkL47[p]
                                                      << "] "
                                                         "["
                                                         "e"
                                                         ": "
                                                      << (e) << "] ";
        full = false;
      }
    }
    if (full) {
      (muu() << __FUNCTION__ << "#" << 118 << ": ") << "["
                                                       "x"
                                                       ": "
                                                    << (x) << "] "
                                                    << "is full";
      add = true;
    }
  }
  long long ans = 1;
  for (int i = 1; i < nax; ++i)
    for (int k = 0; k < __exP__QkL47[i].first; ++k) ans = ans * i % mod;
  if (add) ans++;
  ans %= mod;
  printf("%lld\n", ans);
}