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;
using uint = unsigned int;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &item) {
  out << '(' << item.first << ", " << item.second << ')';
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  for (const auto &item : v) out << item << ' ';
  return out;
}
const double PI = acos(-1);
const int P = 3000010;
struct ftype {
  double a, b;
  ftype(double a = 0, double b = 0) : a(a), b(b) {}
  ftype conj() { return ftype(a, -b); }
  friend ftype operator+(const ftype &x, const ftype &y) {
    return ftype(x.a + y.a, x.b + y.b);
  }
  friend ftype operator-(const ftype &x, const ftype &y) {
    return ftype(x.a - y.a, x.b - y.b);
  }
  friend ftype operator*(const ftype &x, const ftype &y) {
    return ftype(x.a * y.a - x.b * y.b, x.a * y.b + x.b * y.a);
  }
  friend ftype operator/(const ftype &x, int y) {
    return ftype(x.a / y, x.b / y);
  }
};
int cnt[P];
ftype polar(double ang) { return ftype(cos(ang), sin(ang)); }
int rev(int x, int sz) {
  int ans = 0;
  for (int i = 0; i < sz; ++i)
    if (x & (1 << i)) ans |= (1 << (sz - 1 - i));
  return ans;
}
vector<ftype> fft(vector<ftype> p) {
  int i, sz, n = p.size();
  for (sz = 0; (1 << sz) < n; ++sz)
    ;
  for (int i = 0; i < n; ++i)
    if (i < rev(i, sz)) swap(p[i], p[rev(i, sz)]);
  for (int len = 2; len <= n; len <<= 1) {
    double angle = 2 * PI / len;
    ftype wlen = ftype(cos(angle), sin(angle));
    for (int i = 0; i < n; i += len) {
      ftype w = 1;
      for (int j = 0; j < len / 2; ++j) {
        ftype u = p[i + j] + w * p[i + j + len / 2];
        ftype v = p[i + j] - w * p[i + j + len / 2];
        p[i + j] = u;
        p[i + j + len / 2] = v;
        w = w * wlen;
      }
    }
  }
  return p;
}
vector<int> multiply(const vector<int> &a, const vector<int> &b) {
  int sz = 2 * max(a.size(), b.size());
  while (__builtin_popcount(sz) != 1) ++sz;
  vector<ftype> na, nc;
  vector<int> c;
  na.resize(sz);
  for (int i = 0; i < a.size(); ++i) na[i].a = a[i];
  for (int i = 0; i < b.size(); ++i) na[i].b = b[i];
  auto r = fft(na);
  for (int i = 0; i < r.size(); ++i) {
    ftype x = r[i];
    ftype y = r[i == 0 ? i : r.size() - i].conj();
    ftype ai = (x + y) / 2;
    ftype bi = (x - y) / 2 * ftype(0, -1);
    nc.push_back(ai * bi);
  }
  auto vc = fft(nc);
  reverse(vc.begin() + 1, vc.end());
  for (auto val : vc) c.push_back(round(val.a / vc.size()));
  return c;
}
vector<int> solve(const vector<int> &exps, int l, int r) {
  if (l == r) return vector<int>(exps[l] + 1, 1);
  int mid = (l + r) / 2;
  auto vl = solve(exps, l, mid);
  auto vr = solve(exps, mid + 1, r);
  return multiply(vl, vr);
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, p;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> p, ++cnt[p];
  vector<int> exps;
  for (int i = 1; i < P; ++i)
    if (cnt[i]) exps.push_back(cnt[i]);
  auto v = solve(exps, 0, exps.size() - 1);
  cout << v[n / 2] << '\n';
  return 0;
}
