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;
inline int read() {
  char c = getchar();
  int x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
struct modint {
  int x;
  modint(int o = 0) { x = o; }
  modint &operator=(int o) { return x = o, *this; }
  modint &operator+=(modint o) {
    return x = x + o.x >= 998244353 ? x + o.x - 998244353 : x + o.x, *this;
  }
  modint &operator-=(modint o) {
    return x = x - o.x < 0 ? x - o.x + 998244353 : x - o.x, *this;
  }
  modint &operator*=(modint o) { return x = 1ll * x * o.x % 998244353, *this; }
  modint &operator^=(int b) {
    modint a = *this, c = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) c *= a;
    return x = c.x, *this;
  }
  modint &operator/=(modint o) { return *this *= o ^= 998244353 - 2; }
  modint &operator+=(int o) {
    return x = x + o >= 998244353 ? x + o - 998244353 : x + o, *this;
  }
  modint &operator-=(int o) {
    return x = x - o < 0 ? x - o + 998244353 : x - o, *this;
  }
  modint &operator*=(int o) { return x = 1ll * x * o % 998244353, *this; }
  modint &operator/=(int o) { return *this *= ((modint(o)) ^= 998244353 - 2); }
  template <class I>
  friend modint operator+(modint a, I b) {
    return a += b;
  }
  template <class I>
  friend modint operator-(modint a, I b) {
    return a -= b;
  }
  template <class I>
  friend modint operator*(modint a, I b) {
    return a *= b;
  }
  template <class I>
  friend modint operator/(modint a, I b) {
    return a /= b;
  }
  friend modint operator^(modint a, int b) { return a ^= b; }
  friend bool operator==(modint a, int b) { return a.x == b; }
  friend bool operator!=(modint a, int b) { return a.x != b; }
  bool operator!() { return !x; }
  modint operator-() { return x ? 998244353 - x : 0; }
};
const modint G = 3, Ginv = modint(1) / 3;
struct poly {
  vector<modint> a;
  modint &operator[](int i) { return a[i]; }
  int size() { return a.size(); }
  void resize(int n) { a.resize(n); }
};
inline poly one() {
  poly a;
  a.a.push_back(1);
  return a;
}
int rev[4000005];
inline int ext(int n) {
  int k = 0;
  while ((1 << k) < n) ++k;
  return k;
}
inline void init(int k) {
  int n = 1 << k;
  for (register int i = (0); i <= (n - 1); ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
void ntt(poly &a, int k, int typ) {
  int n = 1 << k;
  for (register int i = (0); i <= (n - 1); ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int mid = 1; mid < n; mid <<= 1) {
    modint wn = (typ > 0 ? G : Ginv) ^ ((998244353 - 1) / (mid << 1));
    for (int r = mid << 1, j = 0; j < n; j += r) {
      modint w = 1;
      for (int k = 0; k < mid; ++k, w = w * wn) {
        modint x = a[j + k], y = w * a[j + k + mid];
        a[j + k] = x + y, a[j + k + mid] = x - y;
      }
    }
  }
  if (typ < 0) {
    modint inv = modint(1) / n;
    for (register int i = (0); i <= (n - 1); ++i) a[i] *= inv;
  }
}
poly operator*(poly a, poly b) {
  int n = (int)a.size() + (int)b.size() - 1, k = ext(n);
  a.resize(1 << k), b.resize(1 << k), init(k);
  ntt(a, k, 1), ntt(b, k, 1);
  for (register int i = (0); i <= ((1 << k) - 1); ++i) a[i] *= b[i];
  ntt(a, k, -1), a.resize(n);
  return a;
}
poly init1(int n) {
  poly a;
  a.resize(n);
  for (register int i = (0); i <= (n - 1); ++i) a[i] = 1;
  return a;
}
int n;
map<int, int> mp;
struct cmp {
  bool operator()(poly a, poly b) { return a.size() > b.size(); }
};
priority_queue<poly, vector<poly>, cmp> q;
int main() {
  n = read();
  for (register int i = (1); i <= (n); ++i) mp[read()]++;
  for (auto it : mp) q.push(init1(it.second + 1));
  while (q.size() > 1) {
    poly a = q.top();
    q.pop();
    poly b = q.top();
    q.pop();
    q.push(a * b);
  }
  poly res = q.top();
  cout << res[n / 2].x;
  return 0;
}
