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 A implements Runnable {
	public static void main (String[] args) {new Thread(null, new A(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		FFT fft = new FFT();
		int n = fs.nextInt();
		int MAX = 3000300;
		int[] freq = new int[MAX];
		for(int i = 0; i < n; i++) {
			freq[fs.nextInt()]++;
		}
		
		sort(freq);
		
		PriorityQueue<long[]> pq = new PriorityQueue(new Comp1());
		for(int i = freq.length-1; i >= 0; i--) {
			if(freq[i] == 0) break;
			long[] tmp = new long[freq[i]+1];
			Arrays.fill(tmp, 1);
			pq.add(tmp);
		}
		
		while(pq.size() > 1) {
			long[] a = pq.poll();
			long[] b = pq.poll();
			long[] c = fft.multiplyPrecise(a, b);
			pq.add(c);
		}
		
		long[] fin = pq.poll();
		out.println(fin[n/2]);
		
		out.close();
	}
	
	void sort(int[] a) {
		Random rand = new Random();
		int n = a.length;
		for(int i = 0; i < n; i++) {
			int x = rand.nextInt(n);
			int y = rand.nextInt(n);
			int t = a[x]; a[x] = a[y]; a[y] = t;
		}
		Arrays.sort(a);
	}
	
	class Comp1 implements Comparator<long[]> {
		public int compare(long[] one, long[] two) {
			return Integer.compare(one.length, two.length);
		}
	}
	
	static long MOD = 998244353;
	
	// SET maxk appropriately!!! ~log(maxn) //%
	static class FFT {
	    static final int maxk = 21, maxn = (1 << maxk) + 1;
	    // Init: wR, wI, rR, rI, aR, aI   to   new double[maxn] !!!
	    //#
	    static 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]; //$
	    static int n, k, lastk = -1, dp[] = new int[maxn];

	    static 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;
	                }
	            }
	        }
	    }

	    static 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;
	    }
	    static void fft2(double[][] xr, double[][] xi, boolean inv) {
	        n = xr[0].length;
	        k = Integer.numberOfTrailingZeros(n);
	        for (int i = 0; i < xr.length; i++) {
	            for (int j = 0; j < n; j++) { aR[j] = xr[i][j];  aI[j] = xi[i][j]; }
	            fft(inv);
	            for (int j=0;j<n;j++){xr[i][j] = aR[j] / (inv ? n : 1);  xi[i][j] = aI[j] / (inv ? -n : 1);}
	        }
	        n = xr.length;
	        k = Integer.numberOfTrailingZeros(n);
	        for (int j = 0; j < xr[0].length; j++) {
	            for (int i = 0; i < n; i++) { aR[i] = xr[i][j];  aI[i] = xi[i][j]; }
	            fft(inv);
	            for (int i=0;i<n;i++){xr[i][j] = aR[i] / (inv ? n : 1);  xi[i][j] = aI[i] / (inv ? -n : 1);}
	        }
	    }
	    static long[][] multiply2(long[][] a, long[][] b) {
	        int n1, n2;
	        for (n1 = 1; n1 < a.length + b.length - 1; n1 <<= 1) {}
	        for (n2 = 1; n2 < a[0].length + b[0].length - 1; n2 <<= 1) {}
	        double[][] ar = new double[n1][n2], ai = new double[n1][n2];
	        double[][] br = new double[n1][n2], bi = new double[n1][n2];
	        for (int i = 0; i < a.length; i++) for(int j=0;j<a[i].length;j++) ar[i][j] = a[i][j];
	        for (int i = 0; i < b.length; i++) for(int j=0;j<b[i].length;j++) br[i][j] = b[i][j];
	        fft2(ar,ai,false); fft2(br,bi,false);
	        for (int i = 0; i < n1; i++) {
	            for(int j = 0; j < n2; j++) {
	                double r1 = ar[i][j], r2 = br[i][j];
	                double i1 = ai[i][j], i2 = bi[i][j];
	                double real = r1 * r2 - i1 * i2;
	                ai[i][j] = i1 * r2+ i2*r1;
	                ar[i][j] = real;
	            }
	        }
	        fft2(ar,ai,true);  long[][] result = new long[n1=a.length+b.length-1][n2=a[0].length+b[0].length-1];
	        for (int i = 0; i < n1; i++)
	            for(int j = 0; j < n2; j++) result[i][j] = Math.round(ar[i][j]);
	        return result;
	    }
	    //#
	    static 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;
	    }
	    //$
	    //#
	    static long[] multiplyOr(long[] eq1, long[] eq2) {
	        int n = Math.max(eq1.length, eq2.length);
	        if((n & (n-1)) != 0)
	            n = Integer.highestOneBit(n)*2;
	        eq1 = fftOr(eq1, n, false);
	        eq2 = fftOr(eq2, n, false);
	        for(int i=0;i<eq1.length;i++)
	            eq1[i] *= eq2[i];
	        eq1 = fftOr(eq1, n, true);
	        return eq1;
	    }
	    //$
	    // To use: FFT both, product, iFFT (n is next power of 2)
	    static long[] fftOr(long[] arr, int n, boolean invert) {
	        long[] ans = Arrays.copyOf(arr, n);
	        for (int b = 1; b < n; b <<= 1)
	            for (int i = 0; i < n; i++) {
	                if ((i & b) != 0) continue;
	                ans[i + b] += invert ? -ans[i] : ans[i];
	            }
	        return ans;
	    }
	    static long[] fftXor(long[] arr, int n, boolean invert) {
	        long[] ans = Arrays.copyOf(arr, n);
	        for (int b = 1; b < n; b <<= 1)
	            for (int i = 0; i < n; i++) {
	                if((i & b) != 0) continue;
	                long u = ans[i], v = ans[i+b];
	                ans[i] = u + v;  ans[i + b] = u - v;
	            }
	        if (invert) for (int i = 0; i < n; i++) ans[i] /= n;
	        return ans;
	    }
	}

	class FastScanner {
		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 FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, 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+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;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}