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;
const unsigned maxdeg = 200010;
const unsigned mod = 998244353;
const unsigned prim = 5;
constexpr unsigned degree = maxdeg;
constexpr unsigned digit = 32 - __builtin_clz(degree);
constexpr unsigned bfsize = (1 << (digit + 1));
constexpr unsigned mask = bfsize - 1;
template <unsigned mod, unsigned prim = 0>
struct ModInt {
  int64_t x;
  ModInt() : x(0) {}
  ModInt(int64_t a) : x(a >= 0 ? a % mod : (a % mod + mod) % mod) {}
  inline unsigned getmod() const { return mod; }
  inline ModInt getprim() const { return ModInt(prim); }
  inline ModInt &operator+=(const ModInt &rhs) {
    x = x + rhs.x < mod ? x + rhs.x : x + rhs.x - mod;
    return *this;
  }
  inline ModInt &operator-=(const ModInt &rhs) {
    x = x - rhs.x < 0 ? mod + x - rhs.x : x - rhs.x;
    return *this;
  }
  inline ModInt &operator*=(const ModInt &rhs) {
    x = x * rhs.x % mod;
    return *this;
  }
  inline ModInt &operator/=(const ModInt &rhs) { return *this *= rhs.inv(); }
  inline ModInt modpow(uint64_t n) {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  inline ModInt inv() const { return ModInt(x).modpow(mod - 2); }
  inline ModInt operator-() const { return ModInt(-x); }
  inline ModInt operator+(const ModInt &rhs) const { return ModInt(x) += rhs; }
  inline ModInt operator-(const ModInt &rhs) const { return ModInt(x) -= rhs; }
  inline ModInt operator*(const ModInt &rhs) const { return ModInt(x) *= rhs; }
  inline ModInt operator/(const ModInt &rhs) const { return ModInt(x) /= rhs; }
  inline bool operator==(const ModInt &rhs) const { return x == rhs.x; }
  inline bool operator!=(const ModInt &rhs) const { return x != rhs.x; }
  friend ostream &operator<<(ostream &os, const ModInt &rhs) {
    return os << rhs.x;
  }
  friend istream &operator>>(istream &is, ModInt &rhs) {
    int64_t i;
    is >> i;
    rhs = ModInt(i);
    return is;
  }
};
template <typename Container, typename Mint>
struct NTT {
  Mint *w;
  NTT() {
    w = new Mint[bfsize + 1];
    w[0] = 1;
    Mint x = Mint().getprim().modpow((Mint().getmod() - 1) / bfsize);
    for (unsigned i = 1; i <= bfsize; ++i) w[i] = w[i - 1] * x;
  }
  void bitrev(Container &a, unsigned n) const {
    const int z = __builtin_ctz(n) - 1;
    for (unsigned i = 0, x = 0, j = 0; i < n; ++i) {
      for (x = 0, j = 0; j <= z; ++j) x ^= (i >> j & 1) << (z - j);
      if (x > i) swap(a[x], a[i]);
    }
  }
  void ntt(Container &a, unsigned n) const {
    bitrev(a, n);
    for (unsigned s = 2; s <= n; s <<= 1) {
      unsigned z = s >> 1;
      for (unsigned i = 0; i < n; i += s) {
        for (unsigned k = 0; k < z; ++k) {
          Mint x = a[i + k + z] * w[bfsize / s * k];
          a[i + k + z] = (a[i + k] - x);
          a[i + k] += x;
        }
      }
    }
  }
  void invntt(Container &a, unsigned n) const {
    ntt(a, n);
    for (unsigned i = 1; i < n / 2; ++i) swap(a[i], a[n - i]);
    Mint inv = Mint(1) / n;
    for (unsigned i = 0; i < n; ++i) a[i] *= inv;
  }
  void Multiply(Container &a, Container b) const {
    unsigned n = a.size() + b.size() - 1, sz = 1;
    while (sz < n) sz <<= 1;
    a.resize(sz, 0);
    b.resize(sz, 0);
    ntt(a, sz);
    ntt(b, sz);
    for (unsigned i = 0; i < sz; ++i) a[i] *= b[i];
    invntt(a, sz);
    a.resize(n);
  }
  Container Inverse(Container a, int n) const {
    unsigned sz = 1;
    while (sz < n) sz <<= 1;
    Container ret;
    ret.resize(n, 0);
    ret += Mint(1) / a[0];
    for (unsigned i = 2; i <= sz; i <<= 1) {
      Container n_pre = a.prefix(i);
      Container n_ret = ret.prefix(2 * i);
      n_pre.resize(2 * i, 0);
      n_ret.resize(2 * i, 0);
      ntt(n_pre, 2 * i);
      ntt(n_ret, 2 * i);
      for (unsigned j = 0; j < 2 * i; ++j) n_pre[j] *= n_ret[j] * n_ret[j];
      invntt(n_pre, 2 * i);
      for (unsigned j = 0; j < i; ++j) ret[j] = ret[j] * 2 - n_pre[j];
    }
    return ret;
  }
};
template <typename T>
struct FormalPowerSeries : vector<T> {
  using Poly = FormalPowerSeries;
  static inline const NTT<Poly, T> ntt;
  inline Poly operator+(const Poly &rhs) const { return Poly(*this) += rhs; }
  inline Poly operator+(const T &rhs) const { return Poly(*this) += rhs; }
  inline Poly operator-(const Poly &rhs) const { return Poly(*this) -= rhs; }
  inline Poly operator-(const T &rhs) const { return Poly(*this) -= rhs; }
  inline Poly operator*(const Poly &rhs) const { return Poly(*this) *= rhs; }
  inline Poly operator*(const T &rhs) const { return Poly(*this) *= rhs; }
  inline Poly operator/(const Poly &rhs) const { return Poly(*this) /= rhs; }
  inline Poly operator%(const Poly &rhs) const { return Poly(*this) %= rhs; }
  inline Poly &operator=(const Poly &rhs) {
    unsigned sz = rhs.size();
    this->resize(sz);
    for (unsigned i = 0; i < sz; ++i) (*this)[i] = rhs[i];
    return *this;
  }
  inline Poly operator-() const {
    Poly ret;
    ret.resize(this->size());
    for (unsigned i = 0; i < this->size(); ++i) ret[i] = -(*this)[i];
    return ret;
  }
  inline Poly &operator+=(const Poly &rhs) {
    if (rhs.size() > this->size()) this->resize(rhs.size(), this->zero);
    for (unsigned i = 0; i < rhs.size(); ++i) (*this)[i] += rhs[i];
    return *this;
  }
  inline Poly &operator+=(const T &rhs) {
    (*this)[0] += rhs;
    return *this;
  }
  inline Poly &operator-=(const Poly &rhs) {
    if (rhs.size() > this->size()) this->resize(rhs.size(), this->zero);
    for (unsigned i = 0; i < rhs.size(); ++i) (*this)[i] -= rhs[i];
    return *this;
  }
  inline Poly &operator-=(const T &rhs) { return *this += -rhs; }
  inline Poly &operator*=(const Poly &rhs) {
    ntt.Multiply(*this, rhs);
    return *this;
  }
  inline Poly &operator*=(const T &rhs) {
    for (unsigned i = 0; i < this->size(); i++) (*this)[i] *= rhs;
  }
  inline Poly &operator/=(const Poly &rhs) {
    if (this->size() < rhs.size()) {
      this->clear();
      return *this;
    }
    int n = this->size() - rhs.size() + 1;
    return *this = (rev().prefix(n) * rhs.rev().inv(n)).prefix(n).rev(n);
  }
  Poly prefix(unsigned degree) const {
    Poly ret(*this);
    ret.resize(min(degree, ret.size()));
    return ret;
  }
  Poly rev(int degree = -1) const {
    Poly ret(*this);
    if (degree != -1) ret.resize(degree, ret.zero);
    return ret.reverse();
  }
  inline Poly inv(int degree = -1) const {
    if (degree == -1) degree = this->size();
    return ntt.Inverse(*this, degree);
  }
};
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  using FPS = FormalPowerSeries<ModInt<mod, prim>>;
  int n;
  cin >> n;
  map<int, int> m;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    m[a]++;
  }
  auto cmp = [&](const FPS &a, const FPS &b) { return a.size() < b.size(); };
  multiset<FPS, decltype(cmp)> s(cmp);
  for (auto &iter : m) {
    auto c = iter.second;
    FPS f;
    f.resize(c + 1);
    for (int i = 0; i <= c; i++) f[i] = 1;
    s.insert(f);
  }
  while (s.size() != 1) {
    auto p = *s.begin();
    s.erase(s.begin());
    auto q = *s.begin();
    s.erase(s.begin());
    s.insert(p * q);
  }
  auto res = *s.begin();
  cout << res[n / 2] << endl;
  return 0;
}
