#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;
  sort(a.begin(), a.end());
  int ans = 1;
  function<int(int, int)> gcd = [&](int a, int b) { return b ? gcd(b, a % b) : a; };
  for (int i = 0; i < n; ++i)
    ans = ans * (ll)gcd(a[i], i) % 998244353;
  cout << ans;

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

Niwango-kun has \\(N\\) chickens as his pets. The chickens are identified by numbers \\(1\\) to \\(N\\), and the size of the \\(i\\)-th chicken is a positive integer \\(a_i\\).

\\(N\\) chickens decided to take each other's hand (wing) and form some cycles. The way to make cycles is represented by a permutation \\(p\\) of \\(1, \ldots , N\\). Chicken \\(i\\) takes chicken \\(p_i\\)'s left hand by its right hand. Chickens may take their own hand.

Let us define the cycle containing chicken \\(i\\) as the set consisting of chickens \\(p_i, p_{p_i}, \ldots, p_{\ddots_i} = i\\). It can be proven that after each chicken takes some chicken's hand, the \\(N\\) chickens can be decomposed into cycles.

The beauty \\(f(p)\\) of a way of forming cycles is defined as the product of the size of the smallest chicken in each cycle. Let \\(b_i \ (1 \leq i \leq N)\\) be the sum of \\(f(p)\\) among all possible permutations \\(p\\) for which \\(i\\) cycles are formed in the procedure above.

Find the greatest common divisor of \\(b_1, b_2, \ldots, b_N\\) and print it \\({\rm mod} \ 998244353\\).

Constraints

* \\(1 \leq N \leq 10^5\\)
* \\(1 \leq a_i \leq 10^9\\)
* All numbers given in input are integers

Input

Input is given from Standard Input in the following format:


\(N\)
\(a_1\) \(a_2\) \(\ldots\) \(a_N\)


Output

Print the answer.

Examples

Input

2
4 3


Output

3


Input

4
2 5 2 5


Output

2

### Response

```cpp
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;
  sort(a.begin(), a.end());
  int ans = 1;
  function<int(int, int)> gcd = [&](int a, int b) { return b ? gcd(b, a % b) : a; };
  for (int i = 0; i < n; ++i)
    ans = ans * (ll)gcd(a[i], i) % 998244353;
  cout << ans;

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

```