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;
using Cd = complex<double>;
namespace std {
  template<>
  Cd& Cd::operator*=(const Cd& y) {
    double a = this->real();
    double b = this->imag();
    double c = y.real();
    double d = y.imag();
    return *this=Cd(a*c-b*d, a*d+b*c);
  }
}
 
template<class C>
struct FastFourierTransform{
    static constexpr double PI=acos(-1);
 
    static void dft(vector<C>&f){
        int n=f.size();
		int s=__lg(n);
	
		static vector<vector<C>>w(30);
		w[0]=vector<C>(1,C(1.0,0.0));
		for(int i=1;i<=s;i++){
			if(w[i].size())continue;
			w[i]=vector<C>(1<<i);
			const double t=2*PI/(1<<i);
			for(int j=0;j<1<<i;j++)w[i][j]=(j&1)?polar(1.0,j*t):w[i-1][j>>1];
		}
 
        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++){
			for(int i=0;i<n;i+=1<<m){
				for(int j=0;j<1<<m-1;j++){
					C f0=f[i+j],f1=w[m][j]*f[i+j+(1<<m-1)];
					f[i+j]=f0+f1;
					f[i+j+(1<<m-1)]=f0-f1;
				}
			}
		}
	}
	static void idft(vector<C>&f){
		dft(f);
		reverse(f.begin()+1,f.end());
		double in=1.0/f.size();
		for(int i=0;i<f.size();i++)f[i]*=in;
	}
 
    static vector<i64> convolute(vector<i64> A, vector<i64> B){
        int n=1<<__lg(A.size()+B.size()-2)+1;
        vector<C>g(n),h(n);
        for(int i=0;i<A.size();i++)g[i]=A[i];
        for(int i=0;i<B.size();i++)h[i]=B[i];
 
        dft(g);
        dft(h);
        for(int i=0;i<n;i++)g[i]*=h[i];
        idft(g);
 
        vector<i64>AB(A.size()+B.size()-1);
        for(int i=0;i<AB.size();i++)AB[i]=g[i].real()+0.5;
        return AB;
    }
};
using FFT=FastFourierTransform<complex<double>>;

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<i64> & a, const std::vector<i64> & b) {
			return a.size() < b.size();
		}
	};

	std::multiset<std::vector<i64>, cmp> polies;
	for(auto v: mp) {
		std::vector<i64> 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(FFT::convolute(*it1, *it2));
		polies.erase(it1);
		polies.erase(it2);
	}

	std::vector<i64> pol = *polies.begin();
	i64 ans = *std::max_element(begin(pol), end(pol));
	printf("%lld\n", ans);
	return 0;
}
