#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, N) for(int i = 0; i < int(N); i++)
#define rep1(i, N) for (int i = 1; i <= int(N); i++)
#define fs first
#define sc second
#define pb push_back
#define PB push_back
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

template <uint MD> struct ModInt {
    using M = ModInt;
    uint v;
    ModInt() : v{0} {}
    ModInt(ll _v) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M(0) - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return (*this).pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<998244353>;

int main() {
    int n;
    cin >> n;
    V<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());


    // naive solution
/*    V<ll> sm(n+1);
    V<int> idx(n);
    iota(idx.begin(), idx.end(), 0);

    do {
        V<bool> used(n);
        ll buf = 1; int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            cnt++;
            int p = i;
            ll mi = TEN(18);
            do {
                mi = min(mi, a[p]);
                used[p] = true;
                p = idx[p];
            } while (p != i);
            buf *= mi;
        }
        sm[cnt] += buf;
    } while (next_permutation(idx.begin(), idx.end()));

    for (auto d: sm) cout << d << ", ";
    cout << endl;

    ll ans = 0;
    for (auto d: sm) ans = gcd(ans, d);
    cout << ans << endl;*/

    Mint ans = 1;
    for (int i = 0; i < n; i++) {
        ans *= gcd(i, a[i]);
    }
    cout << ans.v << endl;
    return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, N) for(int i = 0; i < int(N); i++)
#define rep1(i, N) for (int i = 1; i <= int(N); i++)
#define fs first
#define sc second
#define pb push_back
#define PB push_back
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

template <uint MD> struct ModInt {
    using M = ModInt;
    uint v;
    ModInt() : v{0} {}
    ModInt(ll _v) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M(0) - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return (*this).pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<998244353>;

int main() {
    int n;
    cin >> n;
    V<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());


    // naive solution
/*    V<ll> sm(n+1);
    V<int> idx(n);
    iota(idx.begin(), idx.end(), 0);

    do {
        V<bool> used(n);
        ll buf = 1; int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            cnt++;
            int p = i;
            ll mi = TEN(18);
            do {
                mi = min(mi, a[p]);
                used[p] = true;
                p = idx[p];
            } while (p != i);
            buf *= mi;
        }
        sm[cnt] += buf;
    } while (next_permutation(idx.begin(), idx.end()));

    for (auto d: sm) cout << d << ", ";
    cout << endl;

    ll ans = 0;
    for (auto d: sm) ans = gcd(ans, d);
    cout << ans << endl;*/

    Mint ans = 1;
    for (int i = 0; i < n; i++) {
        ans *= gcd(i, a[i]);
    }
    cout << ans.v << endl;
    return 0;
}
```