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>
const int N = 5.3e5 + 535, P = 998244353, G = 3;
int pw(int x, int y) {
  int r = 1;
  for (; y; y >>= 1, x = (unsigned long long)x * x % P)
    if (y & 1) r = (unsigned long long)r * x % P;
  return r;
}
int lim, rev[N], w[N];
void init(int n) {
  int l = 32 - __builtin_clz(n - 1);
  lim = 1 << l;
  for (int i = 0, ri = 0; i < lim; ++i) {
    rev[i] = ri;
    for (int k = lim >> 1; (ri ^= k) < k;) k >>= 1;
  }
  int wn = pw(G, (P - 1) >> l);
  w[lim >> 1] = 1;
  for (int i = (lim >> 1) + 1; i < lim; ++i)
    w[i] = (unsigned long long)w[i - 1] * wn % P;
  for (int i = (lim >> 1) - 1; i; --i) w[i] = w[i << 1];
  lim = l;
}
int _inv[N];
struct ___init {
  ___init() {
    _inv[1] = 1;
    for (int i = 2; i < N; i++)
      _inv[i] = unsigned long long(P - P / i) * _inv[P % i] % P;
  }
} __init;
void md(int &x) { x += x >> 31 & P; }
struct poly {
  std::vector<int> v;
  inline poly() {}
  inline poly(int n) : v(n) {}
  inline poly(const poly &rhs) : v(rhs.v) {}
  inline poly(const std::vector<int> &rhs) : v(rhs) {}
  inline size_t size() { return v.size(); }
  inline bool empty() { return v.empty(); }
  inline void resize(int n) { v.resize(n); }
  inline void clear() { v.clear(); }
  inline void shl() { v.insert(v.begin(), 0); }
  void shrink() {
    while (!v.empty() && !v.back()) v.pop_back();
  }
  inline static int len(int n) { return 1 << (32 - __builtin_clz(n - 1)); }
  inline int &operator[](int i) { return v[i]; }
  void deriv() {
    for (int i = 1; i < v.size(); i++)
      v[i - 1] = (unsigned long long)i * v[i] % P;
    v.pop_back();
  }
  void intg() {
    shl();
    for (int i = 1; i < v.size(); i++)
      v[i] = (unsigned long long)v[i] * _inv[i] % P;
  }
  void dft(int n) {
    static unsigned long long tmp[N];
    int ofs = lim - __builtin_ctz(n);
    resize(n);
    if (n <= 1) return;
    for (int i = 0; i < n; ++i) tmp[rev[i] >> ofs] = v[i];
    for (int i = 0; i < n; i += 2) {
      int x = tmp[i], y = tmp[i + 1];
      tmp[i] = x + y, tmp[i + 1] = x + P - y;
    }
    for (int i = 2; i < n; i <<= 1)
      for (int j = 0; j < n; j += i << 1)
        for (int k = 0; k < i; ++k) {
          int y = (unsigned long long)tmp[j + i + k] * w[i + k] % P;
          tmp[j + i + k] = tmp[j + k] + P - y, tmp[j + k] += y;
        }
    for (int i = 0; i < n; ++i) v[i] = tmp[i] % P;
  }
  void idft(int n) {
    dft(n);
    if (n <= 1) return;
    std::reverse(v.begin() + 1, v.end());
    int tmp = P - (P - 1) / n;
    for (int i = 0; i < n; i++) v[i] = (unsigned long long)v[i] * tmp % P;
  }
  void mul(poly rhs) {
    int n = len(size() + rhs.size() - 1);
    dft(n), rhs.dft(n);
    for (int i = 0; i < n; i++) v[i] = (unsigned long long)v[i] * rhs[i] % P;
    idft(n), shrink();
  }
  void inv() {
    std::vector<int> va(1);
    va[0] = pw(v[0], P - 2);
    poly a;
    int n = size(), m = len(n);
    v.resize(m), v.swap(va);
    for (int i = 2; i <= m; i <<= 1) {
      a.resize(i);
      for (int j = 0; j < i; j++) a[j] = va[j];
      a.dft(i << 1), dft(i << 1);
      for (int j = 0; j < (i << 1); j++)
        v[j] = v[j] * (2 + P - (unsigned long long)v[j] * a[j] % P) % P;
      idft(i << 1);
      resize(i);
    }
    resize(n);
  }
  void ln() {
    poly f0 = *this;
    int n = size();
    deriv(), f0.inv(), mul(f0), resize(n), intg(), resize(n);
  }
  void exp() {
    std::vector<int> va(1);
    va[0] = 1;
    poly a;
    int n = size(), m = len(n);
    v.resize(m), v.swap(va);
    for (int i = 2; i <= m; i *= 2) {
      a = *this, a.resize(i), a.ln();
      for (int j = 0; j < i; j++) a[j] = (va[j] + !j + P - a[j]) % P;
      mul(a);
      resize(i);
    }
    resize(n);
  }
  void solve() {
    std::vector<int> va(v);
    int n = size();
    for (int i = 2; i < n; i++)
      for (int j = 0; j < n; j += i) {
        v[j] = i & 1 ? (v[j] + va[j]) % P : (v[j] + P - va[j]) % P;
      }
    exp();
  }
} a;
std::map<int, int> mp;
int n, m, ans;
int main() {
  scanf("%d", &n);
  for (int i = 1, x; i <= n; i++) scanf("%d", &x), mp[x]++;
  init((n + 1) * 2);
  a.resize(n + 1);
  m = mp.size();
  for (auto [_, y] : mp)
    for (int i = y + 1, j = 1; i <= n; i += y + 1, j++)
      a[i] = (a[i] + P - _inv[j]) % P;
  for (int i = 1; i <= n; i++)
    a[i] = (a[i] + (unsigned long long)m * _inv[i]) % P;
  a.exp();
  for (int i = 0; i <= n; i++) ans = std::max(ans, a[i]);
  printf("%d\n", ans);
}
