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 <iostream>
#define mod 998244353
#include <cstdio>
#define int long long
using namespace std;
int a[3000005],dp[300005],qzh[300005],jc[300005],jcinv[300005];
inline int ksm(int x,int y)
{
	int rtn=1;
	while(y)
	{
		if(y&1)
			rtn*=x,rtn%=mod;
		x*=x,x%=mod,y>>=1;
	}
	return rtn;
}
inline int C(int x,int y)
{
	return jc[x]*jcinv[y]%mod*jcinv[x-y]%mod;
}
signed main(int argc, char** argv) {
	jc[0]=1;
	for(int i=1;i<=200000;i++)
		jc[i]=jc[i-1]*i%mod,jcinv[i]=ksm(jc[i],mod-2);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		++a[t];
		qzh[i]=1;
	}
	int cnt=0;
	for(int i=1;i<=3000000;i++)
	{
		if(a[i]==1)
			++cnt;
	}
	n>>=1;
	qzh[0]=dp[0]=1;
	for(int i=1;i<=n;i++)
		dp[i]=C(cnt,i),qzh[i]=(qzh[i-1]+dp[i])%mod;
	//for(int i=1;i<=n;i++)
	//	cout << dp[i] << " ";
	for(int i=1;i<=3000000;i++)
	{
		if(a[i]>1)
		{
			for(int j=n;j>=0;j--)
			{
				if(j-a[i]-1>=0) dp[j]-=qzh[j-a[i]-1];
				dp[j]+=qzh[j-1]+mod;
				dp[j]%=mod;
			}
			qzh[0]=dp[0];
			for(int j=1;j<=n;j++)
				qzh[j]=(qzh[j-1]+dp[j])%mod;
		}
	}
	cout << dp[n];
	return 0;
}