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>
const long long M = 1e9 + 7;
using namespace std;
long long ans = 1;
long pr[2000005], primeid[2000005], cnt[2000005], nump = 0, n, x, i, j, k, tmp,
                                                  listp[2000005], id[2000005];
vector<long> maxid[2000005], num[2000005];
bool f[2000005] = {1, 1}, fl[2000005], vis[2000005], isp[2000005], plus1s;
bool cmp(vector<long> a, vector<long> b) { return a.size() > b.size(); }
int main() {
  for (i = 2; i <= 2000005 - 5; i++) {
    if (!f[i]) pr[++nump] = i, primeid[i] = nump;
    for (j = 1; j <= nump && i * pr[j] <= 2000005 - 5; j++) {
      f[i * pr[j]] = 1;
      if (i % pr[j] == 0) break;
    }
  }
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> x;
    if (cnt[x] == 0)
      cnt[x] = 1, fl[x] = 1, id[x] = i, maxid[x].push_back(i);
    else {
      long p = 0, q = 1;
      listp[1] = x - 1;
      while (p < q) {
        p++;
        tmp = listp[p];
        for (j = 1; j <= nump && tmp >= pr[j]; j++) {
          long s = 0;
          while (tmp % pr[j] == 0) s++, tmp /= pr[j];
          if (s > 0 && fl[pr[j]])
            q++, listp[q] = pr[j] - 1, fl[pr[j]] = 0, maxid[pr[j]].clear();
          if (s > cnt[pr[j]]) {
            cnt[pr[j]] = s, maxid[pr[j]].clear();
            maxid[pr[j]].push_back(p == 1 ? i : id[listp[p] + 1]);
          } else if (s == cnt[pr[j]] && s != 0)
            maxid[pr[j]].push_back(p == 1 ? i : id[listp[p] + 1]);
          if (!f[tmp]) j = primeid[tmp] - 1;
        }
      }
    }
  }
  for (i = 1; i <= nump; i++)
    for (j = 0; j < maxid[pr[i]].size(); j++)
      num[maxid[pr[i]][j]].push_back(pr[i]);
  sort(num + 1, num + n + 1, cmp);
  for (i = 1; i <= n; i++) {
    bool pp = 0;
    for (j = 0; j < num[i].size(); j++)
      if (!vis[num[i][j]]) vis[num[i][j]] = 1, pp = 1;
    if (!pp) {
      plus1s = 1;
      break;
    }
  }
  for (i = 2; i < 2000005; i++)
    for (j = 1; j <= cnt[i]; j++) ans = ans * i % M;
  if (plus1s) ans = (ans + 1) % M;
  cout << ans;
}