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 \}.
#include <bits/stdc++.h>
using namespace std;
long long qpow(long long x, long long y) {
  if (y < 0) y += 998244353 - 1;
  long long res = 1;
  while (y) {
    if (y & 1) res = res * x % 998244353;
    x = x * x % 998244353;
    y = y / 2;
  }
  return res;
}
long long rev[65536 * 8];
long long isp[65536 * 8];
void curse(vector<long long> &v) {
  while (v.size() > 65536 * 8 / 4) v.pop_back();
}
void ntt(long long a[], long long n, long long typ) {
  for (long long i = 0; i < n; i++)
    if (rev[i] > i) swap(a[i], a[rev[i]]);
  for (long long i = 1; i < n; i <<= 1) {
    long long w = qpow(3, (998244353 - 1) / (i + i) * typ);
    for (long long j = 0; j < n; j += i + i)
      for (long long k = j, wx = 1; k < j + i; k++, wx = wx * w % 998244353) {
        long long e = a[k], r = a[k + i] * wx % 998244353;
        a[k] = (e + r) % 998244353, a[k + i] = (e + 998244353 - r) % 998244353;
      }
  }
  if (typ < 0) {
    long long kl = qpow(n, -1);
    for (long long i = 0; i < n; i++) a[i] = a[i] * kl % 998244353;
  }
}
long long a[65536 * 8], b[65536 * 8];
void ntt(long long n) {
  ntt(a, n, 1);
  ntt(b, n, 1);
  for (long long i = 0; i < n; i++) a[i] = a[i] * b[i] % 998244353;
  ntt(a, n, -1);
}
vector<long long> ntt(vector<long long> &va, vector<long long> &vb) {
  long long n;
  long long sa = va.size(), sb = vb.size();
  for (long long i = 0; i < sa; i++) a[i] = va[i];
  for (long long i = 0; i < sb; i++) b[i] = vb[i];
  while (!isp[sa]) sa++;
  while (!isp[sb]) sb++;
  n = max(sa, sb) * 2;
  for (long long i = 0; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << isp[n] - 2);
  ntt(n);
  vector<long long> o;
  for (long long i = 0; i < n; i++) o.push_back(a[i]);
  for (long long i = 0; i < n; i++) a[i] = b[i] = 0;
  curse(o);
  return o;
}
vector<long long> vs[65536 * 8];
long long n;
map<long long, long long> ump;
long long cnt[65536 * 8];
multiset<pair<long long, long long> > plan;
long long zip() {
  long long x = (*plan.begin()).second;
  plan.erase(plan.begin());
  return x;
}
signed main() {
  for (long long i = 0; (1 << i) < 65536 * 8; i++) isp[1 << i] = i + 1;
  scanf("%lld", &n);
  long long tot = 0, m = n / 2;
  while (n--) {
    long long x;
    scanf("%lld", &x);
    if (!ump[x]) ump[x] = ++tot;
    cnt[ump[x]]++;
  }
  for (long long i = 1; i <= tot; i++) {
    cnt[i]++;
    while (cnt[i]--) vs[i].push_back(1);
    plan.insert(make_pair(vs[i].size(), i));
  }
  while (plan.size() >= 2) {
    long long x = zip();
    long long y = zip();
    vs[x] = ntt(vs[x], vs[y]);
    plan.insert(make_pair(vs[x].size(), x));
  }
  printf("%lld\n", vs[zip()][m]);
  return 0;
}
