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...));
}

template<typename T>
class polynomial {
	using value_type = T;
	using size_type = size_t;

	std::vector<value_type> data;
	
	public:
	polynomial() : data(1, 0) {}
	polynomial(const size_type & N) : data(N, 0) {}
	const value_type eval(const value_type & x) {
		value_type ret = data[0], tmp = x;
		for(int i = 1; i < data.size(); i++) {
			ret += data[i] * tmp;
			tmp *= x;
		}
		return ret;
	}

	void resize(const size_type & N) { data.resize(N); }
	value_type & operator[](const size_type & k) { return data[k]; }
	const size_type degree() { return data.size() - 1; }
	const size_type size() const { return data.size(); }
};

namespace fast_fourier_transform {
	using Real = double;
	using Complex = std::complex<Real>;
	using poly = polynomial<Complex>;
	
	const Real PI = 3.14159265358979323846264338;

	const poly DFT(poly f) {
		const int N = f.size();
		if(N == 1) return f;
		
		poly f0(N / 2);
		poly f1(N / 2);
		for(int i = 0; i < f0.size(); i++) f0[i] = f[i << 1];
		for(int i = 0; i < f1.size(); i++) f1[i] = f[i << 1 ^ 1];

		poly inv_f0 = DFT(f0);
		poly inv_f1 = DFT(f1);

		poly inv_f(N);
		for(int i = 0; i < f.size(); i++) {
			Complex zeta_n_i = Complex(cos(2. * PI * i / N), sin(2. * PI * i / N));

			inv_f[i] = inv_f0[i % f0.size()] + zeta_n_i * inv_f1[i % f1.size()];
		}
		return inv_f;
	}

	const poly IDFT(poly inv_f) {
		const int N = inv_f.size();

		poly arranged = DFT(inv_f);

		poly f(N);
		for(int i = 0; i < N; i++) f[i] = arranged[(N - i) % N] / Complex(N, 0);
		return f;
	}

	const poly convolution(poly a, poly b) {
		const int sz = a.size() + b.size() - 1;

		int N = 1;
		while(N < sz) N <<= 1;
		a.resize(N);
		b.resize(N);

		poly inv_a = DFT(a);
		poly inv_b = DFT(b);
		poly inv_c(N);
		for(int i = 0; i < N; i++) inv_c[i] = inv_a[i] * inv_b[i];
		return IDFT(inv_c);
	}
};

int main() {
	namespace FFT = fast_fourier_transform;
	using poly = FFT::poly;
	
	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 poly & a, const poly & b) {
			return a.size() < b.size();
		}
	};

	std::multiset<poly, cmp> polies;
	for(auto v: mp) {
		poly 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++;

		auto pol = FFT::convolution(*it1, *it2);
		for(int i = 0; i < pol.size(); i++) pol[i] = (i64)round(pol[i].real());
		polies.insert(pol);
		polies.erase(it1);
		polies.erase(it2);
	}

	poly pol = *polies.begin();

	i64 ans = 0;
	for(int i = 0; i < pol.size(); i++) ans = std::max(ans, (i64)round(pol[i].real()));
	printf("%lld\n", ans);
	return 0;
}
