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 \}.
// Aimi Haraguni >> Konomi Suzuki >> Yui >>  Ikimono Gakari >> Garnidelia >> Kalafina >> Eir Aoi.   .. dude?
 
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
 
#define pb push_back
#define ff  first
#define ss second
#define tm1 first
#define tm2 second.first
#define tm3 second.second
#define sz(x) ll(x.size())
#define fill(x, v) memset(x, v, sizeof(x))
#define all(v) (v).begin(), (v).end()
#define FER(i,a,b) for(ll i=ll(a); i< ll(b); ++i)
#define IFR(i,a,b) for(ll i=ll(a); i>=ll(b); --i )
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
 
#define N 17000005
#define mod1 1000000007
#define mod2 1000000009
#define mod 998244353
#define bas 987625403
#define sqr(x) (ll) (x)*(x)  
#define INF LONG_MAX
#define N1 3200005
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ll, ii > tri;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> set_t;
 
#define trace(...) f(#__VA_ARGS__, __VA_ARGS__)
 
template<typename t> void f(const char* x, t&& val1){
    cout<<x<< " : "<<val1<<endl;
}
 
template<typename t1, typename... t2> void f(const char* x, t1&& val1, t2&&... val2){
    const char* xd=strchr(x+1, ',');
    cout.write(x, xd-x)<<" : "<<val1<<" | ";
    f(xd+1, val2...);
}

ll pw[1<<19];
vector<vi> v;

struct NTT{
	ll root_1, root, root_pw;
	inline ll bp(ll a, ll n){
		if(!n) return 1;
		if(n&1) return (a*bp(a, n-1))%mod;
		ll x=bp(a, n>>1);
		return sqr(x)%mod;
	}
	inline void build(){
		root_pw=1<<20;
		FER(i, 2, 1e5+1) if((bp(i, root_pw))==1){
			root=i;
			break;
		}
		root_1=(bp(root, mod-2));
	}
	inline void fft(vi &a, bool inv){
		ll n=sz(a);
		for(ll i=1, j=0; i<n; i++){
			ll bt=n>>1;
			for(; j&bt; bt>>=1) j^=bt;
			j^=bt;
			if(i<j) swap(a[i], a[j]);
		}
		for(ll len=2; len<=n; len<<=1){
			ll wlen=inv? root_1: root;
			for(ll i=len; i<root_pw; i<<=1){
				wlen=(wlen*wlen)%mod;
			}
			for(ll i=0; i<n; i+=len) {
				ll w=1;
				FER(j, 0, len/2){
					ll u=a[i+j], v=(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=(1LL*w*wlen)%mod;
				}
			}
		}
		if(inv) {
			for(auto &xd: a) xd=int((1LL*xd*pw[sz(a)])%mod);
		}
	}
	inline vi GetConvolution(vi &a, vi &b){
		ll n=1;
		while(n<sz(a)+sz(b)) n<<=1;
		a.resize(n), b.resize(n);
		fft(a, false), fft(b, false);
		FER(i, 0, n) a[i]=(1LL*a[i]*b[i])%mod;
		fft(a, true);
		return a;
	}	
	inline vi BPow(vi &a, ll m) {
		ll n=a.back();
		a.pop_back();
		if(n==1) return a;
		ll b=1;
		while(b<sz(a)*n) b<<=1;
		a.resize(b);
		fft(a, false);
		for(auto &xd: a) xd=bp(xd, n);
		fft(a, true);
		a.resize(m);
		return a;
	}
}ntt;

inline vi solve(ll l, ll r, ll n){
	if(l+1==r) {
		return ntt.BPow(v[l], n);
	}
	ll mid=(l+r)>>1;
	vi x=solve(l, mid, n);
	if(sz(x) > n) x.resize(n);
	vi y=solve(mid, r, n);
	if(sz(y) > n) y.resize(n);
	vi z=ntt.GetConvolution(x, y);
	if(sz(z)>n) z.resize(n);
	return z;
}

int main(){
	fastio;
	ll n; cin>>n;
	FER(i, 1, 2e5+5) pw[i]=ntt.bp(i, mod-2);
	ntt.build();
	map<ll, ll> m, t;
	FER(i, 0, n) {
		ll x; cin>>x;
		m[x]++;
	}
	for(auto xd: m) t[xd.ss]++;
	for(auto xd: t) {
		vi tnt;
		FER(i, 0, xd.ff+1) tnt.pb(1);
		tnt.pb(xd.ss);
		v.pb(tnt);
	}      
	vi ans=solve(0, sz(v), n/2+1);
	cout<<ans.back()<<endl;
	return 0;
}
