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 nearestPowerTwo(int n) {
  int r = 1;
  while (r < n) r <<= 1;
  return r;
}
long long int powerMod(long long int a, long long int b, long long int mod) {
  long long int res = 1;
  b %= mod - 1;
  if (b < 0) b += mod - 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    b >>= 1;
    a = (a * a) % mod;
  }
  return res;
}
template <int p, int g, typename T>
void ntt(vector<T> &A, bool inv) {
  int n = int(A.size());
  for (int i = 1, j = 0; i < n - 1; ++i) {
    for (int k = n >> 1; (j ^= k) < k; k >>= 1)
      ;
    if (i < j) swap(A[i], A[j]);
  }
  vector<long long int> wp(n >> 1, 1);
  for (int k = 1; k < n; k <<= 1) {
    long long int wk = powerMod(g, (inv ? -1 : 1) * (p - 1) / (k << 1), p);
    for (int j = 1; j < k; ++j) wp[j] = (wp[j - 1] * wk) % p;
    for (int i = 0; i < n; i += k << 1) {
      for (int j = 0; j < k; ++j) {
        long long int u = A[i + j], v = (A[i + j + k] * wp[j]) % p;
        A[i + j] = (u + v < p) ? u + v : u + v - p;
        A[i + j + k] = (u - v >= 0) ? u - v : u - v + p;
      }
    }
  }
  if (inv) {
    long long int inv_n = powerMod(n, p - 2, p);
    for (auto &x : A) x = (x * inv_n) % p;
  }
}
const int maxN = 2 * (1e5) + 20;
template <int p = 998244353, int g = 3, typename T>
vector<T> multiply(vector<T> A, vector<T> B) {
  int sz = int(A.size()) + int(B.size()) - 1;
  int size = nearestPowerTwo(sz);
  A.resize(size), B.resize(size);
  ntt<p, g>(A, false);
  ntt<p, g>(B, false);
  for (int i = 0; i < size; i++) A[i] = (long long int)A[i] * B[i] % p;
  ntt<p, g>(A, true);
  A.resize(min(sz, maxN));
  return A;
}
template <typename T>
struct Poly {
  vector<T> P;
  const int p = 1;
  Poly() {}
  Poly(int n, int value = 0) : P(n, value) {}
  Poly(vector<T> A) { P = A; }
  void normalize() {
    while (!P.empty() && !P.back()) P.pop_back();
  }
  inline int size() const { return P.size(); }
  inline void resize(int n) { P.resize(n); }
  T &operator[](int i) { return P[i]; }
  const T &operator[](int i) const { return P[i]; }
  void operator=(vector<T> A) { this->P = A; }
  void operator=(Poly<T> A) { this->P = A.P; }
  T add(T a, T b) {
    if (p == 1) return a + b;
    return a + b < p ? a + b : a + b - p;
  }
  T sub(T a, T b) {
    if (p == 1) return a - b;
    return a - b < 0 ? a - b + p : a - b;
  }
  T mul(T a, T b) {
    if (p == 1) return a * b;
    return (a * b) % p;
  }
  T inv(T n) {
    if (p == 1) return 1 / n;
    return powerMod(n, p - 2, p);
  }
  Poly operator+(const Poly<T> &A) {
    Poly<T> ans(max(int(P.size()), int(A.P.size())));
    for (int i = 0; i < int(ans.size()); i++) {
      T a = 0, b = 0;
      if (i < int(P.size())) a = P[i];
      if (i < int(A.size())) b = A[i];
      ans[i] = add(a, b);
    }
    ans.normalize();
    return ans;
  }
  Poly operator-(const Poly<T> &A) {
    Poly<T> ans(max(int(P.size()), int(A.P.size())));
    for (int i = 0; i < int(ans.size()); i++) {
      T a = 0, b = 0;
      if (i < int(P.size())) a = P[i];
      if (i < int(A.size())) b = A[i];
      ans[i] = sub(a, b);
    }
    ans.normalize();
    return ans;
  }
  Poly operator*(int k) {
    Poly<T> ans(int(P.size()));
    for (int i = 0; i < int(ans.size()); i++) {
      ans[i] = mul(P[i], k);
    }
    return ans;
  }
  Poly operator*(const Poly<T> &A) { return multiply(A.P, P); }
  Poly invert(int d = -1) {
    if (d == -1) d = int(P.size());
    Poly<T> R_n = vector<T>{inv(P[0])};
    while (int(R_n.size()) <= d) {
      int j = 2 * int(R_n.size());
      Poly<T> FF = P;
      FF.resize(j);
      Poly<T> RnF = R_n * FF;
      for (auto &x : RnF.P) x = sub(0, x);
      RnF[0] = add(RnF[0], 2);
      R_n = R_n * RnF;
      R_n.resize(j);
    }
    R_n.resize(d + 1);
    return R_n;
  }
};
template <typename T>
ostream &operator<<(ostream &so, const Poly<T> &A) {
  for (auto x : A.P) so << x << " ";
  return so;
}
const long long int MOD = 998244353;
vector<Poly<long long int> > Polys;
Poly<long long int> multiMultiply(int l, int r) {
  if (l == r) return Polys[l];
  int mid = l + (r - l) / 2;
  return multiMultiply(l, mid) * multiMultiply(mid + 1, r);
}
Poly<long long int> binPow(Poly<long long int> P, long long int b) {
  Poly<long long int> res(1, 1);
  while (b) {
    if (b & 1) res = res * P;
    b >>= 1;
    P = P * P;
  }
  return res;
}
int main() {
  ;
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int n;
  cin >> n;
  map<long long int, long long int> fr;
  for (int i = 0; i < n; i++) {
    long long int x;
    cin >> x;
    fr[x]++;
  }
  vector<long long int> cnt;
  for (auto x : fr) {
    cnt.push_back(x.second);
    Poly<long long int> P(x.second + 2);
    P[0] = 1;
    P[x.second + 1] = MOD - 1;
    Polys.push_back(P);
  }
  int m = nearestPowerTwo(int(Polys.size()));
  Polys.resize(m, Poly<long long int>(1, 1));
  auto ANS = multiMultiply(0, m - 1);
  Poly<long long int> AUX(2);
  AUX[0] = 1;
  AUX[1] = MOD - 1;
  Poly<long long int> INV = binPow(AUX, int(fr.size()));
  ANS = ANS * (INV.invert(maxN));
  cout << ANS[(n + 1) / 2] << '\n';
  return 0;
}
