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>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifdef local
#define readfromfile(file) freopen(file, "r", stdin)
#define debug(...) { cerr << __LINE__ << " : \
     [" << #__VA_ARGS__ << "] = ["; err(__VA_ARGS__); cerr << "]\n";}
template<class T>
void err(T x) { cerr << x;}
template<class T, class...Args>
void err(T x, Args... args) { cerr << x << ", "; err(args...);}
#else
#define debug(...)
#define readfromfile(...)
#define endl '\n'
#define cerr if(0)cout
#define err(...)
#endif
#define fi first
#define se second
#define empb emplace_back
#define bk back
#define ppb pop_back
#define ins insert
#define clr(a, b) memset(a, b, sizeof a)
#define rep(i, n) for(int i = 0; i < n; i++)
#define ls rt << 1
#define rs rt<<1|1
#define inf 0x3f3f3f3f
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> pii;

const int mod = 998244353;
const int G = 3;
namespace NTT {
	inline int add(int x, int y) {
		return (x += y) >= mod ? x - mod : x;
	}

	inline int power(int a, int b) {
		int res = 1;
		for(; b; b >>= 1, a = (ll) a * a % mod)
			if(b & 1) res = (ll) res * a % mod;
		return res;
	}

	int nbase = 1;
	vector<int> rts = {0, 1};
	vector<int> divrts = {0, (1ll << 31) / mod};
	vector<int> rev = {0, 1};

	void prepare(int zeros) {
		if(nbase >= zeros) return;
		rts.resize(1 << zeros);
		divrts.resize(1 << zeros);
		rev.resize(1 << zeros);
		for(int i = 0; i < 1<<zeros; i++) {
			rev[i] = (rev[i>>1]>>1)|((i&1)<<zeros-1);
		}
		while(nbase < zeros) {
			int z = power(G, (mod-1)>>nbase+1);
			for(int i = 1 << nbase - 1; i < 1 << nbase; i++) {
				rts[i << 1] = rts[i];
				divrts[i << 1] = divrts[i];
				rts[i << 1 | 1] = (ll) rts[i] * z % mod;
				divrts[i << 1 | 1] = (static_cast<ll>(rts[i << 1 | 1]) << 31) / mod;
			}
			nbase++;
		}
	}
	void ntt(vector<int> &a, int n = -1) {
		if(n == -1) n = a.size();
		assert((n & (n - 1)) == 0);
		int zeros = __builtin_ctz(n);
		prepare(zeros);
		int shift = nbase - zeros;
		for(int i = 0; i < n; i++) {
			if(i < (rev[i] >> shift)) {
				swap(a[i], a[rev[i]>>shift]);
			}
		}
		for(int i = 1; i < n; i <<= 1) {
			for(int j = 0; j < n; j += i * 2) {
				for(int k = 0; k < i; k++) {
					int z = (ll) a[i + j + k] * rts[i + k] - ((ll) a[i + j + k] * divrts[i + k] >> 31) * mod;
					a[i + j + k] = add(a[j + k], mod - z);
					a[j + k] = add(a[j + k], z);
				}
			}
		}
	}
	vector<int> ta, tb;
	vector<int> multiply(const vector<int> &a, const vector<int> &b, int eq = 0) {
		int l1 = a.size(), l2 = b.size(), need = l1 + l2 - 1;
		int sz = 1 << (32 - __builtin_clz(need - 1));
		if((int) ta.size() < sz) {
			ta.resize(sz);
			tb.resize(sz);
		}
		copy(all(a), ta.begin());
		fill(ta.begin() + l1, ta.begin() + sz, 0);
		ntt(ta, sz);
		if(!eq) {
			copy(all(b), tb.begin());
			fill(tb.begin() + l2, tb.begin() + sz, 0);
			ntt(tb, sz);
		} else copy(ta.begin(), ta.begin() + sz, tb.begin());
		int invsz = power(sz, mod - 2);
		for(int i = 0; i <= (sz >> 1); i++) {
			int j = (sz - 1) & (sz - i);
			int z = (ll) ta[j] * tb[j] % mod * invsz % mod;
			if(i != j) ta[j] = (ll) ta[i] * tb[i] % mod * invsz % mod;
			ta[i] = z;
		}
		ntt(ta, sz);
		return vector<int>(ta.begin(), ta.begin() + need);
	}
}
using namespace NTT;

int tot = 0;
vector<vector<int> > pool;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	readfromfile("in.txt");
	int n;
	cin >> n;
	vector<int> p(n);
	for(int i = 0; i < n; i++) {
		cin >> p[i];
	}
	sort(all(p));
	priority_queue<pii> pq;
	for(int i = 0, j = 0; i < n; i = j) {
		while(j < n && p[i] == p[j]) j++;
		pool.emplace_back(j - i + 1, 1);
		pq.emplace(-(j - i), tot++);
	}
	while(pq.size() > 1) {
		int id1 = pq.top().se;
		pq.pop();
		int id2 = pq.top().se;
		pq.pop();
		pool[id1] = multiply(pool[id1], pool[id2]);
		pq.emplace(-pool[id1].size(), id1);
	}
	int id = pq.top().se, sz = n;
	cout << pool[id][sz / 2] << endl;
	cerr << clock() << " ms\n";
	return 0;
}
