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 ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
using LL = long long;
using PII = pair<int, int>;
 
const int mod = 998244353;
const int root = 973800541;
const int root_1 = 595374802;
const int root_pw = 1 << 20;
 
int inverse(int a) {
	int res = 1;
	for (int n = mod - 2; n > 0; n >>= 1) {
		if (n & 1) res = (res * 1ll * a) % mod;
		a = (a * 1ll * a) % mod;
	}
	return res;
}
 
void ntt(vector<int> & a, bool invert=false) {
    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 = inverse(n);
        for (int & x : a)
            x = (int)(1LL * x * n_1 % mod);
    }
}
void multiply(vector<int> &a,vector<int> &b)
{
    ll p=0;
    int x=sz(a),y=sz(b);
    while((1<<p)<=max(sz(a),sz(b)))
        p=p+1;
    p++;
    ll S = (1<<p);
    a.resize(S,0);
    b.resize(S,0);
    ntt(a);ntt(b);
    for(int i=0;i<S;i++)
        a[i] = (a[i]*1LL*b[i])%mod;
    b.clear();
    ntt(a,true);
    a.resize(x+y,0);
}
const int M=3e6+5;
int freq[M];
std::vector<int> poly[M];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	int x;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		freq[x]++;
	}
	int c=0;
	priority_queue<PII,vector<PII>,greater<PII> > pq;
	for(int i=2;i<M;i++)
	{
		if(freq[i]==0)
			continue;
		poly[c].assign(freq[i]+1,0);
		for(int j=0;j<=freq[i];j++)
			poly[c][j]=1;
		pq.push({sz(poly[c]),c});
		c++;
	}
	while(sz(pq)>1)
	{
		auto A=pq.top();
		pq.pop();
		auto B=pq.top();
		pq.pop();
		multiply(poly[A.ss],poly[B.ss]);
		pq.push({sz(poly[A.ss]),A.ss});
	}
	auto A=pq.top();
	int ans=0;
	for(int i=0;i<sz(poly[A.ss]);i++)
		ans=max(ans,poly[A.ss][i]);
	cout<<ans<<"\n";
	return 0;
}