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;
using LL = long long;
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(int) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, long long>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    long long q = static_cast<long long>(static_cast<long double>(value) *
                                         rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  friend const Type& abs(const Modular& x) { return x.value; }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
using ModType = int;
struct VarMod {
  static ModType value;
};
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
class NumberTheory {
 public:
  NumberTheory(int _n)
      : n(_n),
        is_prime(n + 1, true),
        phi(n + 1),
        div_count(n + 1),
        min_div(n + 1) {
    is_prime[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
      if (is_prime[i]) {
        prime.push_back(i);
        min_div[i] = i;
        phi[i] = i - 1;
      }
      for (int j = 0; j < prime.size() && i * prime[j] <= n; ++j) {
        is_prime[i * prime[j]] = false;
        min_div[i * prime[j]] = prime[j];
        if (i % prime[j] != 0) {
          phi[i * prime[j]] = phi[i] * phi[prime[j]];
        } else {
          phi[i * prime[j]] = phi[i] * prime[j];
          break;
        }
      }
    }
  }
  void GetDivisor() {
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; j += i) {
        ++div_count[j];
      }
    }
  }
  vector<pair<LL, int>> Factor(LL a) {
    vector<pair<LL, int>> ans;
    for (int i : prime) {
      if (1LL * i * i > a) break;
      if (a % i != 0) continue;
      int cnt = 0;
      while (a % i == 0) {
        ++cnt;
        a /= i;
      }
      ans.push_back({i, cnt});
    }
    if (a == 1) return ans;
    for (LL i = n + 1; i * i <= a; ++i) {
      if (a % i != 0) continue;
      int cnt = 0;
      while (a % i == 0) {
        ++cnt;
        a /= i;
      }
      ans.push_back({i, cnt});
    }
    if (a > 1) ans.push_back({a, 1});
    return ans;
  }
  vector<pair<int, int>> FactorFast(int a) {
    vector<pair<int, int>> ans;
    while (a > 1) {
      int t = min_div[a], cnt = 0;
      while (a % t == 0) {
        a /= t;
        ++cnt;
      }
      ans.push_back({t, cnt});
    }
    return ans;
  }
  int QuickPow(int a, int b, int mod) {
    if (b == 0) return 1;
    if (b == 1) return a;
    int t = QuickPow(1LL * a * a % mod, b / 2, mod);
    if (b % 2 == 0) return t;
    return 1LL * t * a % mod;
  }
  bool IsPrime(int m) {
    if (m <= n) return is_prime[m];
    int a = m - 1, b = 0;
    while (a % 2 == 0) {
      a /= 2;
      ++b;
    }
    const int times = 10;
    for (int i = 1; i <= times; ++i) {
      int x = rand() % (m - 2) + 2;
      int v = QuickPow(x, a, m);
      if (v == 1 || v == m - 1) continue;
      int j = 0;
      while (j < b) {
        v = 1LL * v * v % m;
        if (v == m - 1) break;
        ++j;
      }
      if (j == b) return false;
    }
    return true;
  }
  int n;
  vector<bool> is_prime;
  vector<int> prime;
  vector<int> phi;
  vector<int> div_count;
  vector<int> min_div;
};
const int MAXN = 2000010;
NumberTheory nt(MAXN);
int cnt[MAXN];
bool z[MAXN][2];
int f[MAXN], g[MAXN];
void Add(int t) {
  while (t > 1) {
    int a = nt.min_div[t];
    int b = 0;
    while (t % a == 0) {
      t /= a;
      ++b;
    }
    if (b > f[a]) {
      f[a] = b;
      g[a] = 1;
    } else if (b == f[a]) {
      ++g[a];
    }
  }
}
void Delete(int t) {
  while (t > 1) {
    int a = nt.min_div[t];
    int b = 0;
    while (t % a == 0) {
      t /= a;
      ++b;
    }
    if (b == f[a]) --g[a];
  }
}
bool Check(int t) {
  while (t > 1) {
    int a = nt.min_div[t];
    int b = 0;
    while (t % a == 0) {
      t /= a;
      ++b;
    }
    if (b == f[a] && g[a] == 1) return false;
  }
  return true;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  md = 1000000007;
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    ++cnt[a];
  }
  bool add = false;
  for (int i = MAXN - 1; i >= 2; --i) {
    if (cnt[i] == 0) continue;
    if (cnt[i] == 1) {
      if (f[i] == 0) {
        Add(i);
        z[i][0] = true;
      } else {
        Add(i - 1);
        z[i][1] = true;
      }
      continue;
    }
    if (f[i] == 0) {
      Add(i);
      Add(i - 1);
      z[i][0] = z[i][1] = true;
      if (cnt[i] > 2) add = true;
    } else {
      Add(i - 1);
      z[i][1] = true;
      add = true;
    }
  }
  if (!add) {
    for (int i = MAXN - 1; i >= 2; --i) {
      if (z[i][0] && Check(i)) {
        if (z[i][1]) {
          add = true;
          break;
        }
        Delete(i);
        Add(i - 1);
        z[i][1] = true;
      }
      if (z[i][1] && Check(i - 1)) {
        add = true;
        break;
      }
    }
  }
  Mint ans = 1;
  for (int i = 2; i < MAXN; ++i) {
    for (int j = 0; j < f[i]; ++j) ans *= i;
  }
  if (add) ++ans;
  cout << ans << endl;
  return 0;
}