You are given an integer x represented as a product of n its prime divisors p_1 ⋅ p_2, ⋅ … ⋅ p_n. Let S be the set of all positive integer divisors of x (including 1 and x itself).

We call a set of integers D good if (and only if) there is no pair a ∈ D, b ∈ D such that a ≠ b and a divides b.

Find a good subset of S with maximum possible size. Since the answer can be large, print the size of the subset modulo 998244353.

Input

The first line contains the single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of prime divisors in representation of x.

The second line contains n integers p_1, p_2, ..., p_n (2 ≤ p_i ≤ 3 ⋅ 10^6) — the prime factorization of x.

Output

Print the maximum possible size of a good subset modulo 998244353.

Examples

Input


3
2999999 43 2999957


Output


3


Input


6
2 3 2 3 2 2


Output


3

Note

In the first sample, x = 2999999 ⋅ 43 ⋅ 2999957 and one of the maximum good subsets is \{ 43, 2999957, 2999999 \}.

In the second sample, x = 2 ⋅ 3 ⋅ 2 ⋅ 3 ⋅ 2 ⋅ 2 = 144 and one of the maximum good subsets is \{ 9, 12, 16 \}.
#include<bits/stdc++.h>

using namespace std;

int n;
map<int, int> cnt;

struct Polynomial {
    using LL = long long;
    static const int mod = 998244353;
    static const int root = 15311432;
    static const int rootExp = 1 << 23;

    int add(int a, int b) {
        a += b;
        return a >= mod ? a - mod : a;
    }
    int sub(int a, int b) { return add(a, mod - b); }
    int mul(int a, int b) { return (int)( (LL)a * b % mod); }
    int binPw(int a, int exp) {
        int ret = 1;
        for (; exp; exp >>= 1, a = mul(a, a) ) if (exp & 1) ret = mul(ret, a);
        return ret;
    }

    vector<int> coef;
    Polynomial(int nA = 0) { coef.assign(nA, 0); }
    bool operator < (const Polynomial& _) const { return coef.size() > _.coef.size(); }


    int reverseBit(int val, int lgN) {
        int ret = 0;
        for (int i = 0; i < lgN; ++i) if ( (val >> i) & 1) ret |= 1 << (lgN - 1 - i);
        return ret;
    }

    void ntt(int nA, bool invert = false) {
        coef.resize(nA);
        int lgN = __lg( (int)coef.size() );

        for (int i = 0; i < (int)coef.size(); ++i) if (i < reverseBit(i, lgN) ) {
            swap(coef[i], coef[reverseBit(i, lgN)]);
        }

        int invRoot = binPw(root, mod - 2);
        for (int len = 2; len <= (int)coef.size(); len <<= 1) {
            int wLen = (invert ? root : invRoot);
            for (int i = rootExp; i > len; i >>= 1) wLen = mul(wLen, wLen);

            for (int i = 0; i < (int)coef.size(); i += len) {
                int w = 1;
                for (int j = 0; j < (len >> 1); ++j) {
                    int u = coef[i + j], v = mul(coef[i + j + (len >> 1)], w);
                    coef[i + j] = add(u, v); coef[i + j + (len >> 1)] = sub(u, v);
                    w = mul(w, wLen);
                }
            }
        }

        if (invert) {
            int invN = binPw( (int)coef.size(), mod - 2);
            for (auto &_ : coef) _ = mul(_, invN);
        }
    }

    Polynomial operator * (Polynomial& _) {
        int tmp = (int)coef.size() + (int)_.coef.size() - 1;
        int len = 1; while (len < tmp) len <<= 1;

        ntt(len); _.ntt(len);
        Polynomial ret(len);
        for (int i = 0; i < len; ++i) ret.coef[i] = mul(coef[i], _.coef[i]);
        ret.ntt(len, true);
        ret.coef.resize(tmp);

        return ret;
    }
};

priority_queue<Polynomial> pq;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int p; cin >> p;
        ++cnt[p];
    }

    for (auto _ : cnt) {
        Polynomial cur(_.second + 1);
        fill(cur.coef.begin(), cur.coef.end(), 1);
        pq.push(cur);
    }

    while (pq.size() > 1) {
        auto a = pq.top(); pq.pop();
        auto b = pq.top(); pq.pop();
        pq.push(a * b);
    }

    cout << pq.top().coef[n / 2 + 1];

    return 0;
}
