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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define endl "\n"
 
const int mod = 998244353;
const int root = 565042129;
const int root_1 = 950391366;
const int root_pw = 1<<20;
 
int mod_expo(int a, int b)
{
    int tans = 1;
    a = a%mod;
    while(b != 0)
    {
        if(b&1)
            tans = (1LL*tans*a)%mod;
        a = (1LL*a*a)%mod;
        b /= 2;
    }
    return tans;
}
 
int mod_inv(int a)
{
    return mod_expo(a, mod-2);
}
 
void fft(vector<int> &a, bool invert)
{
    int n = a.size();
    for(int i = 1, j = 0; i < n; i++)
    {
        int bit = n >> 1;
        for(; j&bit; bit >>= 1)
            j ^= bit;
        j ^= bit;
 
        if(i < j)
            swap(a[i], a[j]);
    }
    for(int len = 2; len <= n; len <<= 1)
    {
        int wlen = invert ? root_1 : root;
        for(int i = len; i < root_pw; i <<= 1)
            wlen = (int)((1LL*wlen*wlen)%mod);
        for(int i = 0; i < n; i += len)
        {
            int w = 1;
            for(int j = 0; j < len/2; j++)
            {
                int u = a[i+j], v = (int)((1LL*a[i+j+len/2]*w)%mod);
                a[i+j] = (u + v < mod) ? (u + v) : (u + v - mod);
                a[i+j+len/2] = (u - v >= 0) ? (u - v) : (u - v + mod);
                w = (int)((1LL*w*wlen)%mod);
            }
        }
    }
    if(invert)
    {
        int n_1 = mod_inv(n);
        for(int & x : a)
            x = (int)((1LL*x*n_1)%mod);
    }
}
 
vector<int> multiply(vector<int> &a, vector<int> &b)
{
    vector<int> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while(n < a.size() + b.size()) 
        n <<= 1;
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);
    for(int i = 0; i < n; i++)
        fa[i] = (fa[i]*fb[i])%mod;
    fft(fa, true);
    int rn = a.size()+b.size()-1;
    vector<int> result(rn);
    for(int i = 0; i < rn; i++)
        result[i] = fa[i];
    return result;
}
 
vector<int> poly_expo(vector<int> &a, int b)
{
    vector<int> fa(a.begin(), a.end());
    int n = 1;
    while(n < b*a.size())
        n <<= 1;
    fa.resize(n);
    fft(fa, false);
    for(int i = 0; i < n; i++)
        fa[i] = mod_expo(fa[i], b);
    fft(fa, true);
    int rn = b*(a.size()-1) + 1;
    vector<int> result(rn);
    for(int i = 0; i < rn; i++)
        result[i] = fa[i];
    return result;
}
 
int p[3000005] = {0}, cnt[200005] = {0};
int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        p[x]++;
    }
    for(int i = 0; i < 3000005; i++)
        if(p[i])
            cnt[p[i]]++;
    vector<int> ans(1, 1);
    for(int i = 0; i <= n; i++)
    {
        if(cnt[i])
        {
            vector<int> temp(i+1, 1);
            temp = poly_expo(temp, cnt[i]);
            ans = multiply(temp, ans);
        }
    }
    cout << max(ans[n/2], ans[(n+1)/2]) << endl;
}
