#include <bits/stdc++.h>
namespace IO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf, obuf[1 << 21], *p = obuf;
struct outflush {
  ~outflush() {
    (void)(fwrite(::IO::obuf, 1, ::IO::p - ::IO::obuf, stdout), fflush(stdout),
           ::IO::p = ::IO::obuf);
  }
} flushout;
}  // namespace IO
int rec() {
  int ch;
  while (isspace(ch = (::IO::p1 == ::IO::p2 &&
                               (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                           fread(::IO::ibuf, 1, 1 << 21, stdin),
                                ::IO::p1 == ::IO::p2)
                           ? EOF
                           : *::IO::p1++)))
    ;
  return ch;
}
bool rei(char& c) {
  int ch;
  while (isspace(ch = (::IO::p1 == ::IO::p2 &&
                               (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                           fread(::IO::ibuf, 1, 1 << 21, stdin),
                                ::IO::p1 == ::IO::p2)
                           ? EOF
                           : *::IO::p1++)))
    ;
  if (ch == EOF) return false;
  c = ch;
  return true;
}
bool rei(char* s) {
  if (!rei(*s)) return false;
  int ch;
  while (*++s = ch = (::IO::p1 == ::IO::p2 &&
                              (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                          fread(::IO::ibuf, 1, 1 << 21, stdin),
                               ::IO::p1 == ::IO::p2)
                          ? EOF
                          : *::IO::p1++),
         ch != EOF && !isspace(ch))
    ;
  *s = 0;
  return true;
}
template <class T>
bool rei(T& x) {
  bool f = true;
  int ch;
  for (ch = (::IO::p1 == ::IO::p2 &&
                     (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                 fread(::IO::ibuf, 1, 1 << 21, stdin),
                     ::IO::p1 == ::IO::p2)
                 ? EOF
                 : *::IO::p1++);
       !isdigit(ch);
       ch = (::IO::p1 == ::IO::p2 &&
                     (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                 fread(::IO::ibuf, 1, 1 << 21, stdin),
                     ::IO::p1 == ::IO::p2)
                 ? EOF
                 : *::IO::p1++)) {
    if (ch == EOF) return false;
    f = ch != '-';
  }
  x = 0;
  if (f) do
      x = x * 10 + (ch & 15);
    while (
        isdigit(ch = (::IO::p1 == ::IO::p2 &&
                              (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                          fread(::IO::ibuf, 1, 1 << 21, stdin),
                               ::IO::p1 == ::IO::p2)
                          ? EOF
                          : *::IO::p1++)));
  else
    do x = x * 10 - (ch & 15);
    while (
        isdigit(ch = (::IO::p1 == ::IO::p2 &&
                              (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                          fread(::IO::ibuf, 1, 1 << 21, stdin),
                               ::IO::p1 == ::IO::p2)
                          ? EOF
                          : *::IO::p1++)));
  return true;
}
void pti(const char& c) {
  (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
       (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
   *::IO::p++ = c);
}
void pti(const char* s) {
  while (*s)
    (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
         (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
     *::IO::p++ = *s++);
}
template <class T>
void pti(T x) {
  char buf[sizeof(T) * 3], *p = buf + 1;
  if (x >= 0)
    *buf = (x % 10) | 48, x /= 10;
  else
    (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
         (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
     *::IO::p++ = '-'),
        *buf = (-(x % 10)) | 48, x = -(x / 10);
  while (x) *p++ = (x % 10) | 48, x /= 10;
  while (p != buf)
    (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
         (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
     *::IO::p++ = *--p);
}
template <class T>
void pri(const T& x) {
  pti(x), (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
               (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
           *::IO::p++ = ' ');
}
template <class T>
void prn(const T& x) {
  pti(x), (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
               (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
           *::IO::p++ = '\n');
}
template <class T, class... Args>
bool rei(T&& x, Args&&... args) {
  return rei(std::forward<T>(x)) ? rei(std::forward<Args>(args)...) : false;
}
template <class T, class... Args>
void pti(const T& x, const Args&... args) {
  pti(x), pti(args...);
}
template <class T, class... Args>
void pri(const T& x, const Args&... args) {
  pri(x), pri(args...);
}
template <class T, class... Args>
void prn(const T& x, const Args&... args) {
  pri(x), prn(args...);
}
template <class T1, class T2>
T1& cmax(T1& a, const T2& b) {
  return a < b ? a = b : a;
}
template <class T1, class T2>
T1& cmin(T1& a, const T2& b) {
  return a > b ? a = b : a;
}
template <class T>
T lowbit(const T& x) {
  return x & -x;
}
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXP = 2e6 + 5;
int pw(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) {
      ans = (long long)ans * a % 1000000007;
    }
    b >>= 1;
    a = (long long)a * a % 1000000007;
  }
  return ans;
}
int p[MAXP];
int id[MAXP];
void getp() {
  for (int i = 2, i_end = MAXP - 1; i <= i_end; ++i) {
    if (!p[i]) {
      p[++*p] = i;
      id[i] = *p;
    }
    for (int j = 1, j_end = *p; j <= j_end; ++j) {
      if (i * p[j] >= MAXP) {
        break;
      }
      p[i * p[j]] = 1;
      if (i % p[j] == 0) {
        break;
      }
    }
  }
}
int cnt[MAXP];
int mxt[MAXP];
void calc(int n) {
  for (int i = 1, i_end = *p; i <= i_end; ++i) {
    if (p[i] * p[i] > n) {
      break;
    }
    if (n % p[i] == 0) {
      int tot = 0;
      do {
        n /= p[i];
        ++tot;
      } while (n % p[i] == 0);
      if (tot > cnt[i]) {
        cnt[i] = tot;
        mxt[i] = 0;
      }
      if (tot == cnt[i]) {
        ++mxt[i];
      }
    }
  }
  if (n != 1) {
    if (!cnt[id[n]]) {
      cnt[id[n]] = 1;
    }
    if (cnt[id[n]] == 1) {
      ++mxt[id[n]];
    }
  }
}
int a[MAXN];
bool check(int n) {
  if (id[n]) {
    return cnt[id[n]] != 1 || mxt[id[n]] != 1;
  }
  for (int i = 1, i_end = *p; i <= i_end; ++i) {
    if (p[i] * p[i] > n) {
      break;
    }
    if (n % p[i] == 0) {
      int tot = 0;
      do {
        n /= p[i];
        ++tot;
      } while (n % p[i] == 0);
      if (cnt[i] == tot && mxt[i] == 1) {
        return false;
      }
    }
  }
  if (n != 1) {
    return cnt[id[n]] != 1 || mxt[id[n]] != 1;
  }
  return true;
}
signed main() {
  getp();
  int n;
  rei(n);
  for (int i = 1, i_end = n; i <= i_end; ++i) {
    rei(a[i]);
  }
  sort(a + 1, a + n + 1, greater<int>());
  for (int i = 1, i_end = n; i <= i_end; ++i) {
    if (cnt[id[a[i]]]) {
      --a[i];
      calc(a[i]);
    } else {
      if (!cnt[id[a[i]]]) {
        cnt[id[a[i]]] = 1;
      }
      if (cnt[id[a[i]]] == 1) {
        ++mxt[id[a[i]]];
      }
    }
  }
  int ans = 1;
  for (int i = 1, i_end = *p; i <= i_end; ++i) {
    ans = (long long)ans * pw(p[i], cnt[i]) % 1000000007;
  }
  for (int i = 1, i_end = n; i <= i_end; ++i) {
    if (check(a[i])) {
      ++ans %= 1000000007;
      break;
    }
  }
  prn(ans);
  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>
namespace IO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf, obuf[1 << 21], *p = obuf;
struct outflush {
  ~outflush() {
    (void)(fwrite(::IO::obuf, 1, ::IO::p - ::IO::obuf, stdout), fflush(stdout),
           ::IO::p = ::IO::obuf);
  }
} flushout;
}  // namespace IO
int rec() {
  int ch;
  while (isspace(ch = (::IO::p1 == ::IO::p2 &&
                               (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                           fread(::IO::ibuf, 1, 1 << 21, stdin),
                                ::IO::p1 == ::IO::p2)
                           ? EOF
                           : *::IO::p1++)))
    ;
  return ch;
}
bool rei(char& c) {
  int ch;
  while (isspace(ch = (::IO::p1 == ::IO::p2 &&
                               (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                           fread(::IO::ibuf, 1, 1 << 21, stdin),
                                ::IO::p1 == ::IO::p2)
                           ? EOF
                           : *::IO::p1++)))
    ;
  if (ch == EOF) return false;
  c = ch;
  return true;
}
bool rei(char* s) {
  if (!rei(*s)) return false;
  int ch;
  while (*++s = ch = (::IO::p1 == ::IO::p2 &&
                              (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                          fread(::IO::ibuf, 1, 1 << 21, stdin),
                               ::IO::p1 == ::IO::p2)
                          ? EOF
                          : *::IO::p1++),
         ch != EOF && !isspace(ch))
    ;
  *s = 0;
  return true;
}
template <class T>
bool rei(T& x) {
  bool f = true;
  int ch;
  for (ch = (::IO::p1 == ::IO::p2 &&
                     (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                 fread(::IO::ibuf, 1, 1 << 21, stdin),
                     ::IO::p1 == ::IO::p2)
                 ? EOF
                 : *::IO::p1++);
       !isdigit(ch);
       ch = (::IO::p1 == ::IO::p2 &&
                     (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                 fread(::IO::ibuf, 1, 1 << 21, stdin),
                     ::IO::p1 == ::IO::p2)
                 ? EOF
                 : *::IO::p1++)) {
    if (ch == EOF) return false;
    f = ch != '-';
  }
  x = 0;
  if (f) do
      x = x * 10 + (ch & 15);
    while (
        isdigit(ch = (::IO::p1 == ::IO::p2 &&
                              (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                          fread(::IO::ibuf, 1, 1 << 21, stdin),
                               ::IO::p1 == ::IO::p2)
                          ? EOF
                          : *::IO::p1++)));
  else
    do x = x * 10 - (ch & 15);
    while (
        isdigit(ch = (::IO::p1 == ::IO::p2 &&
                              (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                          fread(::IO::ibuf, 1, 1 << 21, stdin),
                               ::IO::p1 == ::IO::p2)
                          ? EOF
                          : *::IO::p1++)));
  return true;
}
void pti(const char& c) {
  (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
       (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
   *::IO::p++ = c);
}
void pti(const char* s) {
  while (*s)
    (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
         (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
     *::IO::p++ = *s++);
}
template <class T>
void pti(T x) {
  char buf[sizeof(T) * 3], *p = buf + 1;
  if (x >= 0)
    *buf = (x % 10) | 48, x /= 10;
  else
    (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
         (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
     *::IO::p++ = '-'),
        *buf = (-(x % 10)) | 48, x = -(x / 10);
  while (x) *p++ = (x % 10) | 48, x /= 10;
  while (p != buf)
    (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
         (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
     *::IO::p++ = *--p);
}
template <class T>
void pri(const T& x) {
  pti(x), (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
               (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
           *::IO::p++ = ' ');
}
template <class T>
void prn(const T& x) {
  pti(x), (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
               (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
           *::IO::p++ = '\n');
}
template <class T, class... Args>
bool rei(T&& x, Args&&... args) {
  return rei(std::forward<T>(x)) ? rei(std::forward<Args>(args)...) : false;
}
template <class T, class... Args>
void pti(const T& x, const Args&... args) {
  pti(x), pti(args...);
}
template <class T, class... Args>
void pri(const T& x, const Args&... args) {
  pri(x), pri(args...);
}
template <class T, class... Args>
void prn(const T& x, const Args&... args) {
  pri(x), prn(args...);
}
template <class T1, class T2>
T1& cmax(T1& a, const T2& b) {
  return a < b ? a = b : a;
}
template <class T1, class T2>
T1& cmin(T1& a, const T2& b) {
  return a > b ? a = b : a;
}
template <class T>
T lowbit(const T& x) {
  return x & -x;
}
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXP = 2e6 + 5;
int pw(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) {
      ans = (long long)ans * a % 1000000007;
    }
    b >>= 1;
    a = (long long)a * a % 1000000007;
  }
  return ans;
}
int p[MAXP];
int id[MAXP];
void getp() {
  for (int i = 2, i_end = MAXP - 1; i <= i_end; ++i) {
    if (!p[i]) {
      p[++*p] = i;
      id[i] = *p;
    }
    for (int j = 1, j_end = *p; j <= j_end; ++j) {
      if (i * p[j] >= MAXP) {
        break;
      }
      p[i * p[j]] = 1;
      if (i % p[j] == 0) {
        break;
      }
    }
  }
}
int cnt[MAXP];
int mxt[MAXP];
void calc(int n) {
  for (int i = 1, i_end = *p; i <= i_end; ++i) {
    if (p[i] * p[i] > n) {
      break;
    }
    if (n % p[i] == 0) {
      int tot = 0;
      do {
        n /= p[i];
        ++tot;
      } while (n % p[i] == 0);
      if (tot > cnt[i]) {
        cnt[i] = tot;
        mxt[i] = 0;
      }
      if (tot == cnt[i]) {
        ++mxt[i];
      }
    }
  }
  if (n != 1) {
    if (!cnt[id[n]]) {
      cnt[id[n]] = 1;
    }
    if (cnt[id[n]] == 1) {
      ++mxt[id[n]];
    }
  }
}
int a[MAXN];
bool check(int n) {
  if (id[n]) {
    return cnt[id[n]] != 1 || mxt[id[n]] != 1;
  }
  for (int i = 1, i_end = *p; i <= i_end; ++i) {
    if (p[i] * p[i] > n) {
      break;
    }
    if (n % p[i] == 0) {
      int tot = 0;
      do {
        n /= p[i];
        ++tot;
      } while (n % p[i] == 0);
      if (cnt[i] == tot && mxt[i] == 1) {
        return false;
      }
    }
  }
  if (n != 1) {
    return cnt[id[n]] != 1 || mxt[id[n]] != 1;
  }
  return true;
}
signed main() {
  getp();
  int n;
  rei(n);
  for (int i = 1, i_end = n; i <= i_end; ++i) {
    rei(a[i]);
  }
  sort(a + 1, a + n + 1, greater<int>());
  for (int i = 1, i_end = n; i <= i_end; ++i) {
    if (cnt[id[a[i]]]) {
      --a[i];
      calc(a[i]);
    } else {
      if (!cnt[id[a[i]]]) {
        cnt[id[a[i]]] = 1;
      }
      if (cnt[id[a[i]]] == 1) {
        ++mxt[id[a[i]]];
      }
    }
  }
  int ans = 1;
  for (int i = 1, i_end = *p; i <= i_end; ++i) {
    ans = (long long)ans * pw(p[i], cnt[i]) % 1000000007;
  }
  for (int i = 1, i_end = n; i <= i_end; ++i) {
    if (check(a[i])) {
      ++ans %= 1000000007;
      break;
    }
  }
  prn(ans);
  return 0;
}

```