#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
using namespace std;
const int P = 1e9 + 7;
const int up = 2000000;
inline void MAX(int &a, int b) {
  if (a < b) a = b;
}
inline long long quickpow(long long x, int k) {
  long long res = 1;
  while (k) {
    if (k & 1) res = res * x % P;
    x = x * x % P;
    k >>= 1;
  }
  return res;
}
int pri[2001000], pcnt;
bool depri[2001000];
inline void init() {
  depri[1] = true;
  for (int i = 2; i <= up; ++i) {
    if (!depri[i]) pri[++pcnt] = i;
    for (int j = 1; j <= pcnt && i * pri[j] <= up; ++j) {
      depri[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
    }
  }
}
int n;
int bin[2001000];
int cnt[2001000];
bool Flag;
int memo[2001000], mtot;
int jzpcnt[2001000];
inline void Divi(int x) {
  memo[++mtot] = x;
  bool Fg = false;
  for (int j = 1; j <= pcnt && pri[j] * pri[j] <= x; ++j) {
    if (x % pri[j] == 0) {
      int ct = 0;
      while (x % pri[j] == 0) x /= pri[j], ++ct;
      if (ct > cnt[pri[j]])
        Fg = true, cnt[pri[j]] = ct, jzpcnt[pri[j]] = 1;
      else if (ct == cnt[pri[j]])
        ++jzpcnt[pri[j]];
    }
  }
  if (x > 1) {
    if (!cnt[x])
      cnt[x] = 1, Fg = true, jzpcnt[x] = 1;
    else if (cnt[x] == 1)
      ++jzpcnt[x];
  }
  if (!Fg) Flag = true;
}
inline void check(int x) {
  for (int j = 1; j <= pcnt && pri[j] * pri[j] <= x; ++j) {
    if (x % pri[j] == 0) {
      int ct = 0;
      while (x % pri[j] == 0) x /= pri[j], ++ct;
      if (ct == cnt[pri[j]] && jzpcnt[pri[j]] == 1) return;
    }
  }
  if (x > 1) {
    if (cnt[x] == 1 && jzpcnt[x] == 1) return;
  }
  Flag = true;
}
int main() {
  read(n);
  init();
  for (int i = 1; i <= n; ++i) {
    int x;
    read(x);
    ++bin[x];
  }
  for (int i = up; i; --i)
    if (bin[i]) {
      if (bin[i] == 1) {
        if (!cnt[i]) {
          ++cnt[i];
        } else {
          Divi(i - 1);
        }
      } else {
        if (!cnt[i]) ++cnt[i], --bin[i];
        Divi(i - 1), --bin[i];
        if (bin[i]) Flag = true;
      }
    }
  long long ans = 1;
  for (int i = 1; i <= up; ++i) ans = ans * quickpow(i, cnt[i]) % P;
  if (Flag)
    ++ans;
  else {
    while (mtot) check(memo[mtot--]);
    if (Flag) ++ans;
  }
  printf("%lld\n", (ans % P + P) % P);
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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].

### Response

```cpp
#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
using namespace std;
const int P = 1e9 + 7;
const int up = 2000000;
inline void MAX(int &a, int b) {
  if (a < b) a = b;
}
inline long long quickpow(long long x, int k) {
  long long res = 1;
  while (k) {
    if (k & 1) res = res * x % P;
    x = x * x % P;
    k >>= 1;
  }
  return res;
}
int pri[2001000], pcnt;
bool depri[2001000];
inline void init() {
  depri[1] = true;
  for (int i = 2; i <= up; ++i) {
    if (!depri[i]) pri[++pcnt] = i;
    for (int j = 1; j <= pcnt && i * pri[j] <= up; ++j) {
      depri[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
    }
  }
}
int n;
int bin[2001000];
int cnt[2001000];
bool Flag;
int memo[2001000], mtot;
int jzpcnt[2001000];
inline void Divi(int x) {
  memo[++mtot] = x;
  bool Fg = false;
  for (int j = 1; j <= pcnt && pri[j] * pri[j] <= x; ++j) {
    if (x % pri[j] == 0) {
      int ct = 0;
      while (x % pri[j] == 0) x /= pri[j], ++ct;
      if (ct > cnt[pri[j]])
        Fg = true, cnt[pri[j]] = ct, jzpcnt[pri[j]] = 1;
      else if (ct == cnt[pri[j]])
        ++jzpcnt[pri[j]];
    }
  }
  if (x > 1) {
    if (!cnt[x])
      cnt[x] = 1, Fg = true, jzpcnt[x] = 1;
    else if (cnt[x] == 1)
      ++jzpcnt[x];
  }
  if (!Fg) Flag = true;
}
inline void check(int x) {
  for (int j = 1; j <= pcnt && pri[j] * pri[j] <= x; ++j) {
    if (x % pri[j] == 0) {
      int ct = 0;
      while (x % pri[j] == 0) x /= pri[j], ++ct;
      if (ct == cnt[pri[j]] && jzpcnt[pri[j]] == 1) return;
    }
  }
  if (x > 1) {
    if (cnt[x] == 1 && jzpcnt[x] == 1) return;
  }
  Flag = true;
}
int main() {
  read(n);
  init();
  for (int i = 1; i <= n; ++i) {
    int x;
    read(x);
    ++bin[x];
  }
  for (int i = up; i; --i)
    if (bin[i]) {
      if (bin[i] == 1) {
        if (!cnt[i]) {
          ++cnt[i];
        } else {
          Divi(i - 1);
        }
      } else {
        if (!cnt[i]) ++cnt[i], --bin[i];
        Divi(i - 1), --bin[i];
        if (bin[i]) Flag = true;
      }
    }
  long long ans = 1;
  for (int i = 1; i <= up; ++i) ans = ans * quickpow(i, cnt[i]) % P;
  if (Flag)
    ++ans;
  else {
    while (mtot) check(memo[mtot--]);
    if (Flag) ++ans;
  }
  printf("%lld\n", (ans % P + P) % P);
  return 0;
}

```