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;
int n, p[200020];
const int mod = 1e9 + 7;
bool vis[2000020];
int q[2000020], runs;
int a[2000020], d[2000020];
void ppm() {
  vis[1] = 1;
  for (int i = 2; i < 2000020; i++) {
    if (!vis[i]) q[++runs] = i;
    for (int j = 1; j <= runs && i * q[j] < 2000020; j++) {
      int k = i * q[j];
      vis[k] = 1;
      if (i % q[j] == 0) break;
    }
  }
}
int c[2000020];
int main() {
  ppm();
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  int ans = 1;
  sort(p + 1, p + n + 1);
  int add = 0;
  c[1] = 1;
  for (int i = n; i >= 1; i--) {
    if (c[p[i]]) {
      if (c[p[i] - 1]) {
        add = 1;
        continue;
      } else
        c[p[i] - 1] = 1;
    } else {
      bool flag = 0;
      for (int x = 2 * p[i]; x < 2000020; x += p[i])
        if (c[x]) {
          flag = 1;
          break;
        }
      if (!flag)
        c[p[i]] = 1;
      else {
        if (c[p[i] - 1]) {
          add = 1;
          continue;
        } else
          c[p[i] - 1] = 1;
      }
    }
  }
  for (int i = 2; i < 2000020; i++)
    if (c[i]) {
      int now = i;
      for (int k = 1; q[k] * q[k] <= now; k++)
        if (now % q[k] == 0) {
          int cur = 0;
          while (now % q[k] == 0) {
            now /= q[k];
            cur++;
          }
          if (a[q[k]] < cur)
            a[q[k]] = cur, d[q[k]] = 1;
          else if (a[q[k]] == cur)
            d[q[k]]++;
        }
      if (now == 1) continue;
      if (a[now] < 1)
        a[now] = 1, d[now] = 1;
      else if (a[now] == 1)
        d[now]++;
    }
  if (!add) {
    for (int i = 2; i < 2000020; i++)
      if (c[i]) {
        int now = i;
        bool ok = 0;
        for (int k = 1; q[k] * q[k] <= now; k++)
          if (now % q[k] == 0) {
            int cur = 0;
            while (now % q[k] == 0) {
              now /= q[k];
              cur++;
            }
            if (a[q[k]] == cur && d[q[k]] == 1) {
              ok = 1;
              break;
            }
          }
        if (now > 1 && a[now] == 1 && d[now] == 1) {
          ok = 1;
        }
        if (!ok) {
          c[i] = 0;
          add = 1;
          break;
        }
      }
  }
  for (int i = 2; i < 2000020; i++)
    while (a[i]--) ans = 1ll * ans * i % mod;
  if (add) ans = (ans + 1) % mod;
  cout << ans << endl;
}