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 \}.
// Coached by rainboy
import java.io.*;
import java.util.*;

public class CF1257G extends PrintWriter {
	CF1257G() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1257G o = new CF1257G(); o.main(); o.flush();
	}

	static final int P = 3000000, MD = 998244353;
	long power(int a, int k) {
		if (k == 0)
			return 1;
		long p = power(a, k >> 1);
		p = p * p % MD;
		if ((k & 1) == 1)
			p = p * a % MD;
		return p;
	}
	int[] ww, ww_, invn;
	void init(int n) {
		int h_ = 0;
		while (1 << h_ < n + 1)
			h_++;
		ww = new int[h_ + 1];
		ww_ = new int[h_ + 1];
		invn = new int[h_ + 1];
		for (int h = 0; h <= h_; h++) {
			ww_[h] = (int) power(ww[h] = (int) power(3, MD - 1 >> h), MD - 2);
			invn[h] = (int) power(1 << h, MD - 2);
		}
	}
	static class V {
		int[] aa;
		int n;
		V(int n) {
			this.n = n;
			aa = new int[n + 1]; Arrays.fill(aa, 1);
		}
		V(int[] aa, int n) {
			this.aa = aa; this.n = n;
		}
	}
	void ntt(int[] aa, int n, boolean inverse) {
		for (int i = 1, j = 0; i < n; i++) {
			int b = n;
			do
				j ^= b >>= 1;
			while ((j & b) == 0);
			if (i < j) {
				int tmp = aa[i]; aa[i] = aa[j]; aa[j] = tmp;
			}
		}
		for (int h = 0, b; (b = 1 << h) < n; h++) {
			long w_ = 1, w = inverse ? ww_[h + 1] : ww[h + 1];
			for (int a = 0; a < b; a++) {
				for (int i = a, j; i < n; i += b * 2) {
					long u = aa[i], v = aa[j = i + b] * w_;
					aa[i] = (int) ((u + v) % MD);
					aa[j] = (int) ((u - v) % MD);
				}
				w_ = w_ * w % MD;
			}
		}
	}
	V merge(V u, V v) {
		int n = u.n + v.n;
		int h_ = 0;
		while (1 << h_ < n + 1)
			h_++;
		int n_ = 1 << h_, v_ = invn[h_];
		int[] aa = Arrays.copyOf(u.aa, n_); u.aa = null;
		int[] bb = Arrays.copyOf(v.aa, n_); v.aa = null;
		ntt(aa, n_, false);
		ntt(bb, n_, false);
		for (int i = 0; i < n_; i++)
			aa[i] = (int) ((long) aa[i] * bb[i] % MD);
		ntt(aa, n_, true);
		for (int i = 0; i < n_; i++)
			aa[i] = (int) ((long) aa[i] * v_ % MD);
		return new V(aa, n);
	}
	void main() {
		int n = sc.nextInt();
		init(n);
		int[] kk = new int[P];
		for (int i = 0; i < n; i++) {
			int p = sc.nextInt();
			kk[p]++;
		}
		V[] vv = new V[n * 2]; int head = 0, cnt = 0;
		for (int p = 2; p < P; p++)
			if (kk[p] > 0)
				vv[head + cnt++] = new V(kk[p]);
		while (cnt >= 2) {
			V u = vv[head++], v = vv[head++]; cnt -= 2;
			vv[head + cnt++] = merge(u, v);
		}
		int ans = vv[head].aa[n / 2];
		if (ans < 0)
			ans += MD;
		println(ans);
	}
}
