#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
inline int add(int a, int b) {
  if ((a += b) >= mod) a -= mod;
  return a;
}
inline int dec(int a, int b) {
  if ((a -= b) < 0) a += mod;
  return a;
}
inline int mult(int a, int b) {
  long long t = 1ll * a * b;
  if (t >= mod) t %= mod;
  return t;
}
inline int power(int a, int b) {
  int out = 1;
  while (b) {
    if (b & 1) out = mult(out, a);
    a = mult(a, a);
    b >>= 1;
  }
  return out;
}
int f[2000010];
bool flag[2000010];
vector<int> prime;
void init() {
  memset(f, 0x3f, sizeof(f));
  for (int i = 2; i <= 2000000; i++) {
    if (!flag[i]) f[i] = i, prime.push_back(i);
    for (int j = 0; j < prime.size() && i * prime[j] <= 2000000; j++) {
      f[i * prime[j]] = min(f[i * prime[j]], prime[j]);
      flag[i * prime[j]] = 1;
      if (!(i % prime[j])) break;
    }
  }
}
int n, p[200010], cntmx[2000010], mx[2000010];
int main() {
  init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  sort(p + 1, p + n + 1);
  for (int i = n; i >= 1; i--) {
    if (!mx[p[i]]) {
      cntmx[p[i]] = 1;
      mx[p[i]] = 1;
    } else {
      p[i]--;
      int t = p[i];
      while (t != 1) {
        int p = f[t], cnt = 0;
        while (t % p == 0) t /= p, cnt++;
        if (mx[p] < cnt) {
          cntmx[p] = 1;
          mx[p] = cnt;
        } else if (mx[p] == cnt)
          cntmx[p]++;
      }
    }
  }
  int ad = 0;
  for (int i = 1; i <= n; i++) {
    int t = p[i];
    bool flag = 1;
    while (t != 1) {
      int c = f[t], cnt = 0;
      while (t % c == 0) t /= c, cnt++;
      if (cntmx[c] == 1 && cnt == mx[c]) {
        flag = 0;
        break;
      }
    }
    if (flag) {
      ad = 1;
      break;
    }
  }
  int ans = 1;
  for (auto &x : prime) ans = mult(ans, power(x, mx[x]));
  printf("%d\n", add(ans, ad));
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following 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].

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
inline int add(int a, int b) {
  if ((a += b) >= mod) a -= mod;
  return a;
}
inline int dec(int a, int b) {
  if ((a -= b) < 0) a += mod;
  return a;
}
inline int mult(int a, int b) {
  long long t = 1ll * a * b;
  if (t >= mod) t %= mod;
  return t;
}
inline int power(int a, int b) {
  int out = 1;
  while (b) {
    if (b & 1) out = mult(out, a);
    a = mult(a, a);
    b >>= 1;
  }
  return out;
}
int f[2000010];
bool flag[2000010];
vector<int> prime;
void init() {
  memset(f, 0x3f, sizeof(f));
  for (int i = 2; i <= 2000000; i++) {
    if (!flag[i]) f[i] = i, prime.push_back(i);
    for (int j = 0; j < prime.size() && i * prime[j] <= 2000000; j++) {
      f[i * prime[j]] = min(f[i * prime[j]], prime[j]);
      flag[i * prime[j]] = 1;
      if (!(i % prime[j])) break;
    }
  }
}
int n, p[200010], cntmx[2000010], mx[2000010];
int main() {
  init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  sort(p + 1, p + n + 1);
  for (int i = n; i >= 1; i--) {
    if (!mx[p[i]]) {
      cntmx[p[i]] = 1;
      mx[p[i]] = 1;
    } else {
      p[i]--;
      int t = p[i];
      while (t != 1) {
        int p = f[t], cnt = 0;
        while (t % p == 0) t /= p, cnt++;
        if (mx[p] < cnt) {
          cntmx[p] = 1;
          mx[p] = cnt;
        } else if (mx[p] == cnt)
          cntmx[p]++;
      }
    }
  }
  int ad = 0;
  for (int i = 1; i <= n; i++) {
    int t = p[i];
    bool flag = 1;
    while (t != 1) {
      int c = f[t], cnt = 0;
      while (t % c == 0) t /= c, cnt++;
      if (cntmx[c] == 1 && cnt == mx[c]) {
        flag = 0;
        break;
      }
    }
    if (flag) {
      ad = 1;
      break;
    }
  }
  int ans = 1;
  for (auto &x : prime) ans = mult(ans, power(x, mx[x]));
  printf("%d\n", add(ans, ad));
  return 0;
}

```