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;
const int N = 200005, M = 2000005, P = 1000000007;
int p[N], cnt[M], mm[M], cp[N];
int ip[M], pr[M], mp[M], np;
vector<int> F[N];
int main() {
  int n;
  scanf("%d", &n);
  int flag = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%d", p + i);
  }
  sort(p, p + n);
  for (int i = 2; i < M; ++i) {
    if (!ip[i]) {
      pr[np++] = i;
      mp[i] = i;
      for (int j = i + i; j < M; j += i) {
        if (!ip[j]) {
          ip[j] = 1;
          mp[j] = i;
        }
      }
    }
  }
  for (int i = n - 1; i >= 0; --i) {
    if (!cnt[p[i]]) {
      cnt[p[i]] = 1;
      F[i].push_back(p[i]);
    } else {
      int x = p[i] - 1, lt = 0, t = 0, c = 0;
      while (x != 1) {
        t = mp[x];
        if (t != lt) {
          if (cnt[lt] == c) {
            mm[lt] = 1;
          } else if (cnt[lt] < c) {
            cnt[lt] = c;
            mm[lt] = 0;
          }
          lt = t;
          c = 0;
        }
        c++;
        F[i].push_back(t);
        x /= t;
      }
      if (cnt[t] == c) {
        mm[t] = 1;
      } else if (cnt[t] < c) {
        cnt[t] = c;
        mm[t] = 0;
      }
    }
  }
  long long ans = 1;
  for (int i = 0; i < M; ++i) {
    for (int j = 0; j < cnt[i]; ++j) {
      ans = ans * i % P;
    }
  }
  for (int i = n - 1; i >= 0; --i) {
    int t = 0, lt = 0, c = 0, ok = 0;
    for (int j = 0; j < F[i].size(); ++j) {
      t = F[i][j];
      if (t != lt) {
        if (c == cnt[lt] && !mm[lt]) {
          ok = 1;
        }
        c = 0;
        lt = t;
      }
      c++;
    }
    if (c == cnt[t] && !mm[t]) {
      ok = 1;
    }
    if (!ok) {
      flag = 1;
      break;
    }
  }
  ans += flag;
  printf("%I64d\n", ans % P);
}