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.BufferedInputStream;
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Locale;
import java.util.Scanner;

public class GTask {
    private static final String QUICK_ANSWER = "NO";
    private final Scanner in;
    private final StringBuilder out;

    public GTask(Scanner in, StringBuilder out) {
        this.in = in;
        this.out = out;
    }

    public void solve() throws QuickAnswer {
        int n = nextInt();
        int[] p = nextInts(n);
        int[] counts = counts(p);
        Arrays.sort(counts);
        int pos = counts.length;
        Modulus m = new Modulus(998244353, 100000);
        long res = 1;

        while (pos > 1) {
            if (counts[pos - 2] < 3) break;
            res = m.norm(res * (counts[pos - 2] + 1));
            pos -= 2;
        }
        int cnt2 = 0;
        while (pos > 1) {
            if (counts[pos - 2] == 1) break;
            cnt2++;
            pos -= 2;
        }
        if (pos < 1) {
            while (cnt2-- > 0) res = m.norm(res * 3);
        } else {
            pos += cnt2 * 2;
            res = m.norm(res * m.cnk(pos, pos / 2));
        }
        print(res);
    }

    int[] counts(int[] p) {
        Arrays.sort(p);
        int[] res = new int[p.length];
        int end = 0;
        int cnt = 0;
        int last = p[0];
        for (int val : p) {
            if (val == last) ++cnt;
            else {
                res[end++] = cnt;
                last = val;
                cnt = 1;
            }
        }
        res[end++] = cnt;
        return Arrays.copyOf(res, end);
    }

    // Common functions

    void quickAnswer(String answer) throws QuickAnswer {
        throw new QuickAnswer(answer);
    }

    void quickAnswer() throws QuickAnswer {
        quickAnswer(QUICK_ANSWER);
    }


    static class QuickAnswer extends Exception {
        private String answer;

        public QuickAnswer(String answer) {
            this.answer = answer;
        }
    }

    void print(Object... args) {
        String prefix = "";
        for (Object arg : args) {
            out.append(prefix);
            out.append(arg);
            prefix = " ";
        }
    }

    void println(Object... args) {
        print(args);
        out.append("\n");
    }

    void printsp(Object... args) {
        print(args);
        out.append(" ");
    }

    int nextInt() {
        return in.nextInt();
    }

    long nextLong() {
        return in.nextLong();
    }

    String nextString() {
        String res = in.nextLine();
        return res.trim().isEmpty() ? in.nextLine() : res;
    }

    int[] nextInts(int count) {
        int[] res = new int[count];
        for (int i = 0; i < count; ++i) {
            res[i] = in.nextInt();
        }
        return res;
    }

    long[] nextLongs(int count) {
        long[] res = new long[count];
        for (int i = 0; i < count; ++i) {
            res[i] = in.nextInt();
        }
        return res;
    }

    public static void main(String[] args) {
        doMain(System.in, System.out);
    }

    static void doMain(InputStream inStream, PrintStream outStream) {
        Scanner in = new Scanner(new BufferedInputStream(inStream)).useLocale(Locale.ENGLISH);
        StringBuilder totalOut = new StringBuilder();
        int count = 1;
        //count = in.nextInt();
        while (count-- > 0) {
            try {
                StringBuilder out = new StringBuilder();
                new GTask(in, out).solve();
                totalOut.append(out.toString());
            } catch (QuickAnswer e) {
                totalOut.append(e.answer);
            }
            if (count > 0) {
                totalOut.append("\n");
            }
        }
        outStream.print(totalOut.toString());
    }
}

class Modulus {
    private final int M;
    private final int[] div;
    private final int[] fact;
    private final int[] divFact;


    public Modulus(int m, int cnt) {
        M = m;
        div = new int[cnt + 1];
        fact = new int[cnt + 1];
        divFact = new int[cnt + 1];
        if (cnt < 1) return;
        div[1] = 1;
        fact[0] = 1;
        divFact[0] = 1;
        fact[1] = 1;
        divFact[1] = 1;
        for (int i = 2; i <= cnt; i++) {
            div[i] = calcDiv(i);
            fact[i] = normi(i * (long) fact[i - 1]);
            divFact[i] = normi(div[i] * (long) divFact[i - 1]);
        }
    }

    long norm(long val) {
        val %= M;
        return val < 0 ? M + val : val;
    }

    private int normi(long val) {
        return (int) norm(val);
    }

    int cnk(int n, int k) {
        return normi(norm(fact[n] * (long) divFact[k]) * divFact[n - k]);
    }

    int calcDiv(int i) {
        if (i < div.length && div[i] != 0) {
            return div[i];
        }
        int rem = M % i;
        int d = M / i;
        return normi(-calcDiv(rem) * (long) d);
    }

    long div(int index) {
        return div[index];
    }

    long fact(int index) {
        return fact[index];
    }

    long divFact(int index) {
        return divFact[index];
    }
}
