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

public class g {
	public static void main(String[] args) {new g();}
	FS in = new FS();
	PrintWriter out = new PrintWriter(System.out);

	int n, sz, MAX = 3_000_000;
	int[] prime, freq;
	long MOD = 998244353;
	FFT fft;
	long[] count;
	long[][] poly;

	g() {
		sz = 0;
		n = in.nextInt();
		prime = new int[n];
		freq = new int[MAX + 1];
		for (int i = 0; i < n; i++) {
			int p = in.nextInt();
			if (freq[p] == 0)
				prime[sz++] = p;
			freq[p]++;
		}

		poly = new long[sz][];
		for (int i = 0; i < sz; i++)
			Arrays.fill(poly[i] = new long[freq[prime[i]] + 1], 1L);

		if (sz == 1)
			out.println(1);
		else {
			fft = new FFT();
			count = fft.multiply(poly[0], poly[1]);
			for (int i = 2; i < sz; i++)
				count = fft.multiply(count, poly[i]);
			out.println(count[n / 2]);
		}
		out.close();
	}

	class FFT {
	    int maxk = 21, maxn = (1 << maxk) + 1;
	    // Init: wR, wI, rR, rI, aR, aI   to   new double[maxn] !!!
	    //#
	    double[] wR = new double[maxn],
		    wI = new double[maxn],
		    rR = new double[maxn],
		    rI = new double[maxn],
		    aR  = new double[maxn],
		    aI  = new double[maxn]; //$
	    int n, k, lastk = -1, dp[] = new int[maxn];

	     void fft(boolean inv) {
		if (lastk != k) {
		    lastk = k;  dp[0] = 0;
		    for (int i = 1, g = -1; i < n; i++) {
			if ((i & (i - 1)) == 0) g++;
			dp[i] = dp[i ^ (1 << g)] ^ (1 << (k - 1 - g));
		    }
		    wR[1] = 1;
		    wI[1] = 0;
		    for (int t = 0; t < k - 1; t++) {
			double a = Math.PI / n * (1 << (k - 1 - t));
			double curR = Math.cos(a), curI = Math.sin(a);
			int p2 = (1 << t), p3 = p2 * 2;
			for (int j = p2, k = j * 2; j < p3; j++, k += 2) {
			    wR[k] = wR[j];
			    wI[k] = wI[j];
			    wR[k + 1] = wR[j] * curR - wI[j] * curI;
			    wI[k + 1] = wR[j] * curI + wI[j] * curR;
			}
		    }
		}
		for (int i = 0; i < n; i++) {
		    int d = dp[i];
		    if (i < d) {
			double tmp = aR[i];
			aR[i] = aR[d];
			aR[d] = tmp;
			tmp = aI[i];
			aI[i] = aI[d];
			aI[d] = tmp;
		    }
		}
		if (inv) for (int i = 0; i < n; i++) aI[i] = -aI[i];
		for (int len = 1; len < n; len <<= 1) {
		    for (int i = 0; i < n; i += len) {
			int wit = len;
			for (int it = 0, j = i + len; it < len; it++, i++, j++) {
			    double tmpR = aR[j] * wR[wit] - aI[j] * wI[wit];
			    double tmpI = aR[j] * wI[wit] + aI[j] * wR[wit];
			    wit++;
			    aR[j] = aR[i] - tmpR;
			    aI[j] = aI[i] - tmpI;
			    aR[i] += tmpR;
			    aI[i] += tmpI;
			}
		    }
		}
	    }

	     long[] multiply(long[] a, long[] b) {
		int na = a.length, nb = b.length;
		for (k = 0, n = 1; n < na + nb - 1; n <<= 1, k++) {}
		for (int i = 0; i < n; ++i) {
		    aR[i] = i < na ? a[i] : 0;
		    aI[i] = i < nb ? b[i] : 0;
		}
		fft(false);
		aR[n] = aR[0];
		aI[n] = aI[0];
		double q = -1.0 / n / 4.0;
		for (int i = 0; i <= n - i; ++i) {
		    double tmpR = aR[i] * aR[i] - aI[i] * aI[i];
		    double tmpI = aR[i] * aI[i] * 2;
		    tmpR -= aR[n - i] * aR[n - i] - aI[n - i] * aI[n - i];
		    tmpI -= aR[n - i] * aI[n - i] * -2;
		    aR[i] = -tmpI * q;
		    aI[i] = tmpR * q;
		    aR[n - i] = aR[i];
		    aI[n - i] = -aI[i];
		}
		fft(true);
		long[] ans = new long[n = na + nb - 1]; // ONLY MOD IF NEEDED
		for (int i = 0; i < n; i++) ans[i] = Math.round(aR[i]) % MOD;
		return ans;
	    }
	}

	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch (Exception e) {}
			} return st.nextToken();
		}
		int nextInt() { return Integer.parseInt(next()); }
		long nextLong() { return Long.parseLong(next()); }
		double nextDouble() { return Double.parseDouble(next()); }
	}
}
