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;
struct P {
  long long x;
  long long y;
  bool operator<(const P &a) const { return y > a.y; }
};
vector<int> v;
int a, c, i, b, n, m, k, d;
int o[222173];
int l[2000171];
int j[2233333];
int e[2066661];
int dx[10] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[10] = {1, 0, -1, 0, 1, -1, 1, -1},
    dz[10] = {0, 0, 0, 0, 1, -1};
long long x, y, mod = 1000000007, mod2 = 1000000009, mod3 = 2017;
long long z;
double pi = 3.14159265;
int u[2222221];
queue<int> q;
bool as(P a, P b) {
  if (a.x != b.x) return a.x < b.x;
  return a.y < b.y;
}
bool ai(int a, int b) { return a > b; }
int main() {
  for (int t = 2; t <= 2000000; t++)
    if (!l[t]) {
      l[t] = t;
      v.push_back(t);
      for (long long h = (long long)t * t; h <= 2000000; h += t)
        if (!l[h]) l[h] = t;
    }
  scanf("%d", &a);
  for (int t = 1; t <= a; t++) scanf("%d", &o[t]);
  sort(o + 1, o + a + 1, ai);
  for (int t = 1; t <= a; t++) {
    if (!j[o[t]])
      j[o[t]] = 1, e[o[t]] = 1, u[t] = 1;
    else {
      c = o[t];
      m = 0;
      o[t]--;
      for (; o[t] > 1;) {
        k = l[o[t]];
        int i = 0;
        for (; o[t] % k == 0; o[t] /= k, i++)
          ;
        if (i > j[k])
          j[k] = i, e[k] = 1;
        else if (i == j[k]) {
          e[k]++;
        }
      }
      o[t] = c;
    }
  }
  for (int t = 1; t <= a; t++) {
    if (u[t])
      ;
    else {
      c = o[t];
      m = 0;
      o[t]--;
      for (; o[t] > 1;) {
        k = l[o[t]];
        int i = 0;
        for (; o[t] % k == 0; o[t] /= k, i++)
          ;
        if (i == j[k] && e[k] == 1) {
          m = 1;
        }
      }
      if (!m) d = 1;
    }
  }
  x = 1;
  for (int t = 2; t <= 2000000; t++) {
    for (; j[t]; j[t]--, x *= t, x %= mod)
      ;
  }
  printf("%lld", (x + d) % mod);
}