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 \}.
// In the name of Allah.
// We're nothing and you're everything.
// Ya Ali!
 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 3e6 + 14, mod = 1e9 + 7;
#define REP(i, n) for(int i = 0; i < (n); i++)
typedef ll llint;
namespace FFT {
	const int MAX = 1 << 21;
	const double PII = acos(-1);
	typedef llint value;
	typedef complex<double> comp;

	int N;
	comp omega[MAX];
	comp a1[MAX], a2[MAX];
	comp z1[MAX], z2[MAX];

	void fft(comp *a, comp *z, int m = N) {
		if (m == 1) {
			z[0] = a[0];
		} else {
			int s = N/m;
			m /= 2;

			fft(a, z, m);
			fft(a+s, z+m, m);

			REP(i, m) {
				comp c = omega[s*i] * z[m+i];
				z[m+i] = z[i] - c;
				z[i] += c;
			}
		}
	}

	void mult(value *a, value *b, value *c, int len) {
		N = 2*len;
		while (N & (N-1)) ++N;
		assert(N <= MAX);

		REP(i, N) a1[i] = 0;
		REP(i, N) a2[i] = 0;
		REP(i, len) a1[i] = a[i];
		REP(i, len) a2[i] = b[i];

		REP(i, N) omega[i] = polar(1.0, 2*PII/N*i);
		fft(a1, z1, N);
		fft(a2, z2, N);

		REP(i, N) omega[i] = comp(1, 0) / omega[i];
		REP(i, N) a1[i] = z1[i] * z2[i] / comp(N, 0);
		fft(a1, z1, N);

		REP(i, 2*len) c[i] = round(z1[i].real()) + 0.5;
	}

	void mult_mod(int *a, int *b, int *c, int len, int mod) {
		static llint a0[MAX], a1[MAX];
		static llint b0[MAX], b1[MAX];
		static llint c0[MAX], c1[MAX], c2[MAX];

		REP(i, len) a0[i] = a[i] & 0xFFFF;
		REP(i, len) a1[i] = a[i] >> 16;

		REP(i, len) b0[i] = b[i] & 0xFFFF;
		REP(i, len) b1[i] = b[i] >> 16;

		FFT::mult(a0, b0, c0, len);
		FFT::mult(a1, b1, c2, len);

		REP(i, len) a0[i] += a1[i];
		REP(i, len) b0[i] += b1[i];
		FFT::mult(a0, b0, c1, len);
		REP(i, 2*len) c1[i] -= c0[i] + c2[i];
		
		REP(i, 2*len) c1[i] %= mod;
		REP(i, 2*len) c2[i] %= mod;
		REP(i, 2*len) c[i] = (c0[i] + ((long long) c1[i] << 16) + ((long long) c2[i] << 32)) % mod;
	}
}
#undef REP

map<int, int> cnt;
int n, a[maxn];
vector<int> solve(int l, int r){
	if(r - l == 1)
		return vector<int>(a[l] + 1, 1);
	int mid = (l + r) / 2;
	vector<int> L = solve(l, mid), R = solve(mid, r);
	int real = L.size() + R.size() - 1;
	vector<int> ret(max(L.size(), R.size()) * 2);
	if(L.size() < R.size())
		L.resize(R.size());
	else
		R.resize(L.size());
	FFT::mult_mod(L.data(), R.data(), ret.data(), L.size(), mod);
	ret.resize(real);
	return ret;
}
void shuffle(int l = 0, int r = n){
	if(r - l < 2)
		return ;
	vector<int> L, R;
	for(int i = 0; i < r - l; i++)
		(i & 1 ? L : R).push_back(a[l + i]);
	for(int i = 0; i < r - l; i++)
		a[l + i] = i < L.size() ? L[i] : R[i - L.size()];
	int mid = (l + r) / 2;
	shuffle(l, mid);
	shuffle(mid, r);
}
int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		cnt[x]++;
	}
	n = cnt.size();
	auto it = cnt.begin();
	for(int i = 0; i < n; i++)
		a[i] = it++ -> second;
	//sort(a, a + n);
	//shuffle();
	vector<int> ans = solve(0, n);
	//for(auto x : ans)
	//	cerr << x << ' ';
	//cerr << '\n';
	//assert(*max_element(ans.begin(), ans.end()) == ans[ans.size() / 2]);
	cout << ans[ans.size() / 2] << '\n';
}
