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();}
	JS in = new JS();
	PrintWriter out = new PrintWriter(System.out);

	int n, sz, MAX = 3_000_000;
	int[] prime, freq;
	long MOD = 998244353;
	FFT fft;
	long[][] poly;
	PriorityQueue<long[]> q;

	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]++;
		}

		q = new PriorityQueue<>((a, b) -> a.length - b.length);
		poly = new long[sz][];
		for (int i = 0; i < sz; i++) {
			Arrays.fill(poly[i] = new long[freq[prime[i]] + 1], 1L);
			q.add(poly[i]);
		}
		
		fft = new FFT();
		while (q.size() > 1) {
			long[] p1 = q.poll();
			long[] p2 = q.poll();
			q.add(fft.multiplyPrecise(p1, p2));
		}
		out.println(q.poll()[n / 2]);
		out.close();
	}

	long max(long a, long b) {
		if (a > b)
			return a;
		return b;
	}

	class FFT {
		int maxk = 18, 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;
	    }

	        long[] multiplyPrecise(long[] a, long[] b) {
        long k = (long)(Math.sqrt(MOD));
        long[] a1 = new long[a.length], a2 = new long[a.length];
        long[] b1 = new long[b.length], b2 = new long[b.length];
        for(int i=0;i<a.length;i++) {
            a1[i] = a[i] % k;
            a2[i] = a[i] / k;
        }
        for(int i=0;i<b.length;i++) {
            b1[i] = b[i] % k;
            b2[i] = b[i] / k;
        }
        long[] r11 = multiply(a1, b1), r12 = multiply(a1, b2), r21 = multiply(a2, b1), r22 = multiply(a2, b2);
        long[] res = new long[r11.length];
        for(int i=0;i<res.length;i++)
            res[i] = (k*k*r22[i] + k*(r12[i] + r21[i]) + r11[i]) % MOD;
        return res;
    }
	}

	class JS {
	public int BS = 1<<16;
	public char NC = (char)0;
	byte[] buf = new byte[BS];
	int bId = 0, size = 0;
	char c = NC;
	double num = 1;
	BufferedInputStream in;

	public JS() {
		in = new BufferedInputStream(System.in, BS);
	}

	public JS(String s) throws FileNotFoundException {
		in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
	}

	public char nextChar(){
		while(bId==size) {
			try {
				size = in.read(buf);
			}catch(Exception e) {
				return NC;
			}
			if(size==-1)return NC;
			bId=0;
		}
		return (char)buf[bId++];
	}

	public int nextInt() {
		return (int)nextLong();
	}

	public long nextLong() {
		num=1;
		boolean neg = false;
		if(c==NC)c=nextChar();
		for(;(c<'0' || c>'9'); c = nextChar()) {
			if(c=='-')neg=true;
		}
		long res = 0;
		for(; c>='0' && c <='9'; c=nextChar()) {
			res = (res<<3)+(res<<1)+c-'0';
			num*=10;
		}
		return neg?-res:res;
	}

	public double nextDouble() {
		double cur = nextLong();
		return c!='.' ? cur:cur+(cur < 0 ? -1*nextLong()/num : nextLong()/num);
	}

	public String next() {
		StringBuilder res = new StringBuilder();
		while(c<=32)c=nextChar();
		while(c>32) {
			res.append(c);
			c=nextChar();
		}
		return res.toString();
	}

	public String nextLine() {
		StringBuilder res = new StringBuilder();
		while(c<=32)c=nextChar();
		while(c!='\n') {
			res.append(c);
			c=nextChar();
		}
		return res.toString();
	}

	public boolean hasNext() {
		if(c>32)return true;
		while(true) {
			c=nextChar();
			if(c==NC)return false;
			else if(c>32)return true;
		}
	}
}
}
