You are given an integer x represented as a product of n its prime divisors p1⋅p2,⋅…⋅pn. 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.
The first line contains the single integer n (1≤n≤2⋅105) — the number of prime divisors in representation of x.
The second line contains n integers p1,p2,…,pn (2≤pi≤3⋅106) — the prime factorization of x.
Print the maximum possible size of a good subset modulo 998244353.
3 2999999 43 2999957
3
6 2 3 2 3 2 2
3
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}.
