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 <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MD	998244353
#define X	3000000

int ww[20], ww_[20], vv[20];

long long power(int a, int b) {
	long long p;

	if (b == 0)
		return 1;
	p = power(a, b / 2);
	p = p * p % MD;
	if (b % 2)
		p = p * a % MD;
	return p;
}

void init() {
	int h;

	for (h = 0; h < 20; h++) {
		ww_[h] = power(ww[h] = power(3, MD - 1 >> h), MD - 2);
		vv[h] = power(1 << h, MD - 2);
	}
}

int *resize(int *aa, int n_) {
	int *bb = calloc(n_, sizeof *aa);

	memcpy(bb, aa, n_ * sizeof *aa);
	free(aa);
	return bb;
}

void ntt(int *aa, int n, int inverse) {
	int h, i, j, b, l, r;

	for (j = 1, i = 0; j < n; j++) {
		int tmp;

		b = n;
		do
			i ^= b >>= 1;
		while ((i & b) == 0);
		if (i < j)
			tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
	}
	for (h = 0; (b = 1 << h) < n; h++) {
		int w = inverse ? ww_[h + 1] : ww[h + 1];
		long long w_ = 1;

		for (j = 0; j < b; j++) {
			for (l = j; l < n; l += b * 2) {
				int u, v;

				r = l + b;
				u = aa[l], v = aa[r] * w_ % MD;
				if ((aa[l] = u + v) >= MD)
					aa[l] -= MD;
				if ((aa[r] = u - v) < 0)
					aa[r] += MD;
			}
			w_ = (long long) w_ * w % MD;
		}
	}
}

int *kk_;

int *solve(int l, int r) {
	int *aa, *bb;
	int n, n_, m, h_, i;

	n = 0;
	for (i = l; i < r; i++)
		n += kk_[i];
	h_ = 0;
	while (1 << h_ <= n)
		h_++;
	n_ = 1 << h_;
	if (r - l == 1) {
		aa = calloc(n_, sizeof *aa);
		for (i = 0; i <= n; i++)
			aa[i] = 1;
	} else {
		long long v;

		m = (l + r) / 2;
		aa = resize(solve(l, m), n_);
		bb = resize(solve(m, r), n_);
		ntt(aa, n_, 0);
		ntt(bb, n_, 0);
		for (i = 0; i < n_; i++)
			aa[i] = (long long) aa[i] * bb[i] % MD;
		ntt(aa, n_, 1);
		v = vv[h_];
		for (i = 0; i < n_; i++)
			aa[i] = aa[i] * v % MD;
	}
	return aa;
}

int main() {
	static int *kk, *pp;
	int n, n_, i, x;

	init();
	scanf("%d", &n);
	kk = malloc((X + 1) * sizeof *kk);
	for (i = 0; i < n; i++)
		scanf("%d", &x), kk[x]++;
	kk_ = malloc(n * sizeof *kk_);
	n_ = 0;
	for (x = 0; x <= X; x++)
		if (kk[x])
			kk_[n_++] = kk[x];
	free(kk);
	pp = solve(0, n_);
	printf("%d\n", pp[n / 2]);
	return 0;
}
