#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(2e6) + 17;

int n;
int a[MAXN];

bool read() {
    if (!(cin >> n))
        return false;

    forn (i, n)
        cin >> a[i];
    
    return true;
}

ll gcd(ll a, ll b) {
    for (; b > 0; a %= b, swap(a, b)) { }
    return a;
}

void solve() {
    sort(a, a + n);
    ll ans = 1;

    forn (i, n)
        ans = ans * gcd(a[i], i) % 998244353;

    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
#ifdef SEREZHKA
    freopen("file.in", "r", stdin);
#endif
    
    while (read())
        solve();
    
    return 0;
}


### Prompt

Create a solution in cpp for 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>

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(2e6) + 17;

int n;
int a[MAXN];

bool read() {
    if (!(cin >> n))
        return false;

    forn (i, n)
        cin >> a[i];
    
    return true;
}

ll gcd(ll a, ll b) {
    for (; b > 0; a %= b, swap(a, b)) { }
    return a;
}

void solve() {
    sort(a, a + n);
    ll ans = 1;

    forn (i, n)
        ans = ans * gcd(a[i], i) % 998244353;

    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
#ifdef SEREZHKA
    freopen("file.in", "r", stdin);
#endif
    
    while (read())
        solve();
    
    return 0;
}


```