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;
template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}
constexpr int mod = 7 * 17 * (1 << 23) + 1;
constexpr int omega_max = 23;
constexpr int root = 31;
class NTT {
  using ll = long long;
  std::vector<int> omega;
  int mod_inv(ll a, ll m) {
    ll b = mod, u = 1, v = 0;
    while (b > 0) {
      ll t = a / b;
      a -= t * b;
      std::swap(a, b);
      u -= t * v;
      std::swap(u, v);
    }
    return (u % m + m) % m;
  }
  std::vector<int> fft(std::vector<int> v, bool inv) {
    const int n = v.size();
    int _logn = 0;
    while ((1 << _logn) < n) _logn++;
    assert(1 << _logn == n);
    int ww = omega[_logn];
    if (inv) ww = mod_inv(ww, mod);
    for (int m = n; m >= 2; m >>= 1) {
      const int mh = m >> 1;
      int w = 1;
      for (int i = 0; i < mh; i++) {
        for (int j = i; j < n; j += m) {
          const int k = j + mh;
          int x = v[j] - v[k];
          if (x < 0) x += mod;
          v[j] += v[k];
          if (v[j] >= mod) v[j] -= mod;
          v[k] = (1LL * w * x) % mod;
        }
        w = (1LL * w * ww) % mod;
      }
      ww = (1LL * ww * ww) % mod;
    }
    int i = 0;
    for (int j = 1; j < n - 1; j++) {
      for (int k = n >> 1; k > (i ^= k); k >>= 1)
        ;
      if (j < i) std::swap(v[i], v[j]);
    }
    if (inv) {
      const int inv_n = mod_inv(n, mod);
      for (auto &x : v) {
        x = (1LL * x * inv_n) % mod;
      }
    }
    return v;
  }

 public:
  NTT() {
    omega.resize(omega_max + 1);
    int x = root;
    for (int i = omega_max; i >= 0; i--) {
      omega[i] = x;
      x = (1LL * x * x) % mod;
    }
  }
  std::vector<int> convolution(std::vector<int> f, std::vector<int> g) {
    int sz = 1;
    const int m = f.size() + g.size() - 1;
    while (sz < m) sz *= 2;
    f.resize(sz), g.resize(sz);
    f = this->fft(std::move(f), false);
    g = this->fft(std::move(g), false);
    for (int i = 0; i < sz; i++) {
      f[i] = (1LL * f[i] * g[i]) % mod;
    }
    return this->fft(std::move(f), true);
  }
};
NTT ntt;
vector<int> rec(const vector<int> &cnt, int ma) {
  int n = 1;
  while (n < (int)cnt.size()) n *= 2;
  vector<vector<int>> node(2 * n, vector<int>{1});
  for (int i = 0; i < (int)cnt.size(); i++) {
    node[i + n] = vector<int>(cnt[i] + 1, 1);
  }
  for (int i = n - 1; i >= 0; i--) {
    node[i] = ntt.convolution(node[2 * i], node[2 * i + 1]);
    if (node[i].size() > ma) node[i].resize(ma);
  }
  return node[1];
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    int p;
    cin >> p;
    mp[p]++;
  }
  vector<int> cnt;
  for (auto p : mp) {
    cnt.push_back(p.second);
  }
  sort(cnt.begin(), cnt.end());
  int sz = cnt.size();
  auto ret = rec(cnt, n / 2 + 1);
  cout << ret[n / 2] << endl;
}
