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;
int const TT = 998244353, G = 3;
inline int KSM(int a, int k) {
  int ret = 1 % TT;
  for (; k; k >>= 1, a = 1ll * a * a % TT)
    if (k & 1) ret = 1ll * ret * a % TT;
  return ret;
}
inline int add(int x, int y) {
  if (x + y >= TT)
    return x + y - TT;
  else
    return x + y;
}
inline int sub(int x, int y) {
  if (x - y >= 0)
    return x - y;
  else
    return x - y + TT;
}
namespace Polynom {
vector<int> rev, rt, e = {1}, one = {1};
vector<int> operator+(vector<int> f, vector<int> g) {
  int n = (int)max(f.size(), g.size());
  f.resize(n);
  g.resize(n);
  for (int i = 0; i < n; ++i) f[i] = add(f[i], g[i]);
  return f;
}
vector<int> operator-(vector<int> f, vector<int> g) {
  int n = (int)max(f.size(), g.size());
  f.resize(n);
  g.resize(n);
  for (int i = 0; i < n; ++i) f[i] = sub(f[i], g[i]);
  return f;
}
void getRevRoot(int n) {
  int m = log(n) / log(2) + 1e-7;
  rev.resize(n);
  rt.resize(n);
  for (int i = 1; i < n; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << (m - 1);
  for (int len = 1, uni; len < n; len <<= 1) {
    uni = KSM(G, (TT ^ 1) / (len << 1));
    rt[len] = 1;
    for (int i = 1; i < len; ++i)
      rt[i + len] = 1ll * rt[i + len - 1] * uni % TT;
  }
}
void NTT(vector<int>& f, int n) {
  f.resize(n);
  for (int i = 0; i < n; ++i)
    if (i < rev[i]) swap(f[i], f[rev[i]]);
  for (int len = 1; len < n; len <<= 1)
    for (int i = 0; i < n; i += len << 1)
      for (int j = 0, x, y; j < len; j++) {
        x = f[i + j];
        y = 1ll * f[i + j + len] * rt[j + len] % TT;
        f[i + j] = add(x, y);
        f[i + j + len] = sub(x, y);
      }
}
vector<int> operator*(vector<int> f, vector<int> g) {
  int n = 1, m = (int)f.size() + (int)g.size() - 1, ivn;
  while (n < m) n <<= 1;
  ivn = KSM(n, TT - 2);
  getRevRoot(n);
  NTT(f, n);
  NTT(g, n);
  for (int i = 0; i < n; ++i) f[i] = 1ll * f[i] * g[i] % TT;
  reverse(f.begin() + 1, f.end());
  NTT(f, n);
  f.resize(m);
  for (int i = 0; i < m; ++i) f[i] = 1ll * f[i] * ivn % TT;
  return f;
}
vector<int> polyInv(vector<int> f, int m) {
  if (m == 1) return {KSM(f[0], TT - 2)};
  f.resize(m);
  vector<int> g = polyInv(f, m >> 1), h;
  g.resize(m);
  h.resize(m);
  for (int i = (m >> 1) - 1; ~i; --i) h[i] = (g[i] << 1) % TT;
  int n = m << 1, ivn = KSM(n, TT - 2);
  getRevRoot(n);
  NTT(f, n);
  NTT(g, n);
  for (int i = 0; i < n; ++i) f[i] = 1ll * f[i] * g[i] % TT * g[i] % TT;
  reverse(f.begin() + 1, f.end());
  NTT(f, n);
  for (int i = 0; i < m; ++i) h[i] = sub(h[i], 1ll * f[i] * ivn % TT);
  return h;
}
vector<int> operator~(vector<int> f) {
  int n = 1, m = (int)f.size();
  while (n < m) n <<= 1;
  f = polyInv(f, n);
  f.resize(m);
  return f;
}
vector<int> polyDeri(vector<int> f) {
  if (f.empty()) return f;
  int n = (int)f.size();
  for (int i = 1; i < n; ++i) f[i - 1] = 1ll * f[i] * i % TT;
  f.resize(n - 1);
  return f;
}
vector<int> polyInte(vector<int> f) {
  int n = (int)f.size();
  f.resize(n + 1);
  for (int i = n; ~i; --i) f[i] = 1ll * f[i - 1] * KSM(i, TT - 2) % TT;
  return f;
}
vector<int> polyLn(vector<int> f) {
  int n = (int)f.size();
  f = polyInte((~f) * polyDeri(f));
  f.resize(n);
  return f;
}
vector<int> polyExp(vector<int> f, int n) {
  if (n == 1) return one;
  f.resize(n);
  vector<int> g = polyExp(f, n >> 1);
  g.resize(n);
  return g * (one - polyLn(g) + f);
}
inline vector<int> polyExp(vector<int> f) {
  int n = 1, m = (int)f.size();
  while (n < m) n <<= 1;
  f = polyExp(f, n);
  f.resize(m);
  return f;
}
inline vector<int> operator^(vector<int> f, int x) {
  int n = 0, m = (int)f.size();
  while (n < m - 1 && !f[n]) n++;
  f.erase(f.begin(), f.begin() + n);
  e = {KSM(f.empty() ? 0 : f[0], x)};
  f = polyLn(f);
  f.resize(n = max(0ll, m - 1ll * n * x));
  for (int i = 1; i < n; ++i) f[i] = 1ll * f[i] * x % TT;
  f = polyExp(f);
  reverse(f.begin(), f.end());
  for (int i = m - n; i; --i) f.push_back(0);
  reverse(f.begin(), f.end());
  f.resize(m);
  return f;
}
inline vector<int> operator/(vector<int> f, vector<int> g) {
  int n = f.size(), m = g.size();
  reverse(f.begin(), f.end());
  reverse(g.begin(), g.end());
  f.resize(n - m + 1);
  g.resize(n - m + 1);
  vector<int> ret = f * (~g);
  ret.resize(n - m + 1);
  reverse(ret.begin(), ret.end());
  return ret;
}
inline vector<int> operator%(vector<int> f, vector<int> g) {
  vector<int> ret = f / g;
  ret = f - (g * ret);
  ret.resize(g.size() - 1);
  return ret;
}
}  // namespace Polynom
using namespace Polynom;
vector<int> a_mul[200000 << 2];
void getMula(vector<int> const& a, int k, int l, int r) {
  if (l == r) {
    a_mul[k] = vector<int>(a[l] + 1, 1);
    return;
  }
  int mid = (l + r) >> 1;
  getMula(a, k << 1, l, mid);
  getMula(a, k << 1 | 1, mid + 1, r);
  a_mul[k] = a_mul[k << 1] * a_mul[k << 1 | 1];
}
int main() {
  int n;
  scanf("%d", &n);
  auto mp = map<int, int>();
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    mp[x]++;
  }
  int m = mp.size();
  auto a = vector<int>();
  for (auto p : mp) a.push_back(p.second);
  getMula(a, 1, 0, m - 1);
  cout << a_mul[1][n / 2] << '\n';
}
