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::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

using namespace std;

template<uint32_t mod>
struct ModInt{
	uint32_t a;
	ModInt& s(uint32_t vv){
		a=vv<mod?vv:vv-mod;
		return *this;
	}

    ModInt(int64_t x=0){s(x%mod+mod);}

	ModInt& operator+=(const ModInt &x){return s(a+x.a);}
	ModInt& operator-=(const ModInt &x){return s(a+mod-x.a);}
	ModInt& operator*=(const ModInt &x){
		a=uint64_t(a)*x.a%mod;
		return *this;
	}
	ModInt& operator/=(const ModInt &x){
		*this*=x.inv();
		return *this;
	}

	ModInt operator+(const ModInt &x)const{return ModInt(*this)+=x;}
	ModInt operator-(const ModInt &x)const{return ModInt(*this)-=x;}
	ModInt operator*(const ModInt &x)const{return ModInt(*this)*=x;}
	ModInt operator/(const ModInt &x)const{return ModInt(*this)/=x;}
	bool operator==(const ModInt &x)const{return a==x.a;}
	bool operator!=(const ModInt &x)const{return a!=x.a;}
	bool operator<(const ModInt &x)const{return a<x.a;}

	ModInt operator-()const{return ModInt()-*this;}
	ModInt pow(int64_t n)const{
		ModInt res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}

    ModInt inv()const{return pow(mod-2);}
};

template<uint32_t mod>
istream& operator>>(istream& in,const ModInt<mod>& a){
	return (in>>a.a);
}
template<uint32_t mod>
ostream& operator<<(ostream& out,const ModInt<mod>& a){
	return (out<<a.a);
}
using mint=ModInt<998244353>;

template<class Mint,int32_t root>
struct NumberTheoreticTransform{
	static void ntt(vector<Mint>&f){
		int n=f.size();
        int s=__lg(n);

        for(int i=0,j=1;j<n-1;j++){
            for(int k=n>>1;k>(i^=k);k>>=1);
            if(i>j)swap(f[i],f[j]);
        }

        for(int m=1;m<=s;m++){
            Mint wr=Mint(root).pow(Mint(-1).a>>m);
            for(int i=0;i<n;i+=1<<m){
                Mint w=1;
                for(int j=0;j<1<<m-1;j++){
                    Mint f0=f[i+j],f1=w*f[i+j+(1<<m-1)];
                    f[i+j]=f0+f1;
                    f[i+j+(1<<m-1)]=f0-f1;
                    w*=wr;
                }
            }
        }
	}

    static void intt(vector<Mint>&f){
        reverse(f.begin()+1,f.end());
        ntt(f);
        Mint in=Mint(f.size()).inv();
        for(int i=0;i<f.size();i++)f[i]*=in;
    }

	static vector<Mint>convolute(const vector<Mint>&A,const vector<Mint>&B){
        int n=1<<__lg(A.size()+B.size()-2)+1;
        
        vector<Mint>a=A,b=B;
        a.resize(n);b.resize(n);
        ntt(a);
        ntt(b);
        for(int i=0;i<n;i++)a[i]*=b[i];
        intt(a);
        a.resize(A.size()+B.size()-1);
        return a;
    }
};
using NTT=NumberTheoreticTransform<mint,3>;

int main() {
	int n; scanf("%d", &n); std::vector<int> a(n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);

	std::map<int, int> mp;
	for(auto v: a) mp[v]++;

	struct cmp {
		bool operator ()(const std::vector<mint> & a, const std::vector<mint> & b) {
			return a.size() < b.size();
		}
	};

	std::multiset<std::vector<mint>, cmp> polies;
	for(auto v: mp) {
		std::vector<mint> pol(v.second + 1);
		for(int i = 0; i <= v.second; i++) pol[i] = 1;

		polies.insert(pol);
	}
	
	while(polies.size() > 1) {
		auto it2 = polies.begin();
		auto it1 = it2++;

		polies.insert(NTT::convolute(*it1, *it2));
		polies.erase(it1);
		polies.erase(it2);
	}

	printf("%lld\n", (*polies.begin())[n / 2].a);
	return 0;
}
