#include <bits/stdc++.h>
      
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())

#define pb emplace_back
#define fi first
#define se second

using namespace std;

using ld = long double;
using ll = long long int;

const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ll MOD = 998244353;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> void UNIQUE(vector<T> &a){ a.erase(unique(a.begin(), a.end()), a.end()); }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll in(){long long int x; scanf("%lld", &x); return x;}
ld fin(){double x; scanf("%lf", &x); return x;}
char yuyushiki[1000010]; string stin(){scanf( "%s", yuyushiki ); return yuyushiki;}

// head

vector<int> v, s;
vector<bool> used;
void dfs(int x){
  used[x] = true;
  s.pb(x);
  if(!used[v[x]]){
    dfs(v[x]);
  }
}

const ll N = 100010;

int main(){

  vector<ll> ps(0);
  vector<bool> isp(N, true);
  isp[0] = isp[1] = false;
  FOR(i, 2, N){
    if(isp[i]){
      ps.pb(i);
      for(ll j = i*2; j < N; j += i){
        isp[j] = false;
      }
    }
  }

  ll n = in();
  vector<ll> b(n);
  REP(i, n){
    b[i] = in();
  }

  sort(b.begin(), b.end());
  
  ll res = b[0] % MOD;
  YYS(w, ps){
    ll cur = w;
    ll cnt = 0;
    while(cur <= n - 1){
      cnt += (n - 1) / cur;
      cur *= w;
    }
    for(ll i = w; i < n; i += w){
      ll j = 0;
      cur = b[i];
      while(cur % w == 0){
        cur /= w;
        j++;
      }
      cur = i;
      while(cur % w == 0){
        cur /= w;
        j--;
      }
      if(j < 0){
        cnt += j;
      }
    }
    // cout << w << " " << cnt << endl;
    REP(i, cnt){
      res *= w;
      res %= MOD;
    }
  }

  cout << res << endl;
  
  return 0;
}

### Prompt

In cpp, your task is to solve 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 <bits/stdc++.h>
      
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())

#define pb emplace_back
#define fi first
#define se second

using namespace std;

using ld = long double;
using ll = long long int;

const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ll MOD = 998244353;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> void UNIQUE(vector<T> &a){ a.erase(unique(a.begin(), a.end()), a.end()); }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll in(){long long int x; scanf("%lld", &x); return x;}
ld fin(){double x; scanf("%lf", &x); return x;}
char yuyushiki[1000010]; string stin(){scanf( "%s", yuyushiki ); return yuyushiki;}

// head

vector<int> v, s;
vector<bool> used;
void dfs(int x){
  used[x] = true;
  s.pb(x);
  if(!used[v[x]]){
    dfs(v[x]);
  }
}

const ll N = 100010;

int main(){

  vector<ll> ps(0);
  vector<bool> isp(N, true);
  isp[0] = isp[1] = false;
  FOR(i, 2, N){
    if(isp[i]){
      ps.pb(i);
      for(ll j = i*2; j < N; j += i){
        isp[j] = false;
      }
    }
  }

  ll n = in();
  vector<ll> b(n);
  REP(i, n){
    b[i] = in();
  }

  sort(b.begin(), b.end());
  
  ll res = b[0] % MOD;
  YYS(w, ps){
    ll cur = w;
    ll cnt = 0;
    while(cur <= n - 1){
      cnt += (n - 1) / cur;
      cur *= w;
    }
    for(ll i = w; i < n; i += w){
      ll j = 0;
      cur = b[i];
      while(cur % w == 0){
        cur /= w;
        j++;
      }
      cur = i;
      while(cur % w == 0){
        cur /= w;
        j--;
      }
      if(j < 0){
        cnt += j;
      }
    }
    // cout << w << " " << cnt << endl;
    REP(i, cnt){
      res *= w;
      res %= MOD;
    }
  }

  cout << res << endl;
  
  return 0;
}

```