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;

#define MS(a, b) memset(a, b, sizeof(a))
#define REP(a, b, c) for (register int a = b, _n = c; a <= _n; ++a)
#define DREP(a, b, c) for (register int a = b, _n = c; a >= _n; --a)
#define FOR(a, b, c) for (register int a = b, _n = c; a < _n; ++a)
#define EREP(a, b) for (register int a = head[b]; a; a = edge[a].nxt)
#define MOD(a) (a >= Mod && (a -= Mod))
#define ADD(a) (a < 0 && (a += Mod))

inline int rd () {
    int x = 0; char c = getchar(); bool f = 0;
    while (c < '0' && c != '-') c = getchar();
    if (c == '-') f = 1, c = getchar();
    while (c >= '0') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}

const int SIZE = 1 << 18;
const int Mod = 998244353;

int Pow (int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % Mod;
        b >>= 1;
        a = 1LL * a * a % Mod;
    }
    return res;
}

int n, N;
int p[SIZE], a[SIZE];

int x[19][SIZE], len[19];
int rev[SIZE];
void NTT_init (int n) {
    FOR (i, 1, n) 
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
}
void NTT (int *a, int n, int inv) {
    FOR (i, 1, n) if (i < rev[i])
        swap(a[i], a[rev[i]]);
    for (int mid = 1; mid < n; mid <<= 1) {
        int w0;
        if (inv == 1) w0 = Pow(3, (Mod - 1) / (mid << 1));
        else w0 = Pow((Mod + 1) / 3, (Mod - 1) / (mid << 1));
        for (int i = 0; i < n; i += (mid << 1)) {
            int w = 1;
            FOR (j, 0, mid) {
                int x = a[i + j], y = 1LL * w * a[i + j + mid] % Mod;
                a[i + j] = x + y; MOD(a[i + j]);
                a[i + j + mid] = x - y; ADD(a[i + j + mid]);
                w = 1LL * w * w0 % Mod;
            }
        }
    }
    if (inv == -1) {
        inv = Pow(n, Mod - 2);
        FOR (i, 0, n) a[i] = 1LL * a[i] * inv % Mod;
    }
}
void Solve (int L, int R, int d) {
    if (L == R) {
        len[d] = a[L];
        REP (i, 0, a[L]) x[d][i] = 1;
        return;
    }
    int mid = (L + R) >> 1;
    Solve(L, mid, d + 1);
    len[d] = len[d + 1];
    REP (i, 0, len[d]) x[d][i] = x[d + 1][i];
    Solve(mid + 1, R, d + 1);
    int N = 1;
    while (N <= len[d] + len[d + 1]) N <<= 1;
    NTT_init(N);
    FOR (i, len[d] + 1, N) x[d][i] = 0;
    FOR (i, len[d + 1] + 1, N) x[d + 1][i] = 0;
    NTT(x[d], N, 1);
    NTT(x[d + 1], N, 1);
    FOR (i, 0, N) x[d][i] = 1LL * x[d][i] * x[d + 1][i] % Mod;
    NTT(x[d], N, -1);
    len[d] = len[d] + len[d + 1];
}

void _main () {
    n = rd();
    REP (i, 1, n) p[i] = rd();
    sort(p + 1, p + n + 1);
    REP (i, 1, n) {
        int j = i;
        while (j < n && p[j + 1] == p[i]) ++j;
        a[++N] = j - i + 1;
    }
    Solve(1, N, 0);
    printf ("%d\n", x[0][n / 2]);
}

int main () {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    _main();
    return 0;
}
