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>
istream& operator>>(istream& is, vector<T>& a) {
  for (T& ai : a) is >> ai;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> const& a) {
  os << "[ ";
  for (const T& ai : a) os << ai << " ";
  return os << "]";
}
const int M = 998244353;
const int A = 565042129;
const int AINV = 950391366;
const int N = 1048576;
const int NINV = 998243401;
int pow_mod(int a, int b) {
  int r = 1, c = a;
  while (b) {
    if (b & 1) r = ((long long)r * c) % M;
    if (b >>= 1) c = ((long long)c * c) % M;
  }
  return r;
}
void dft(vector<int>& a, int t) {
  int n = a.size();
  if (n == 1) return;
  int m = n / 2;
  vector<int> a0(m), a1(m);
  for (int i = 0; i < m; ++i) {
    a0[i] = a[2 * i];
    a1[i] = a[2 * i + 1];
  }
  dft(a0, ((long long)t * t) % M);
  dft(a1, ((long long)t * t) % M);
  long long b = 1;
  for (int i = 0; i < m; ++i) {
    a[i] = (a0[i] + b * a1[i]) % M;
    a[i + m] = (a0[i] - b * a1[i]) % M;
    if (a[i + m] < 0) a[i + m] += M;
    b = (b * t) % M;
  }
}
void poly_mul(vector<int>& p, vector<int>& q) {
  int m = p.size() + q.size() - 1;
  int n = N, a = A, ainv = AINV, ninv = NINV;
  while (n >> 1 >= m) {
    n >>= 1;
    a = ((long long)a * a) % M;
    ainv = ((long long)ainv * ainv) % M;
    ninv = (2LL * ninv) % M;
  }
  p.resize(n);
  dft(p, a);
  q.resize(n);
  dft(q, a);
  for (int i = 0; i < n; ++i) p[i] = ((long long)p[i] * q[i]) % M;
  q.clear();
  dft(p, ainv);
  p.resize(m);
  for (int& pi : p) pi = ((long long)pi * ninv) % M;
}
void poly_pow(vector<int>& p, int k) {
  int m = (p.size() - 1) * k + 1;
  int n = N, a = A, ainv = AINV, ninv = NINV;
  while (n >> 1 >= m) {
    n >>= 1;
    a = ((long long)a * a) % M;
    ainv = ((long long)ainv * ainv) % M;
    ninv = (2LL * ninv) % M;
  }
  p.resize(n);
  dft(p, a);
  for (int i = 0; i < n; ++i) p[i] = pow_mod(p[i], k);
  dft(p, ainv);
  p.resize(m);
  for (int& pi : p) pi = ((long long)pi * ninv) % M;
}
int f() {
  int n;
  cin >> n;
  unordered_map<int, int> c;
  for (int i = 0, p; i < n; ++i) {
    cin >> p;
    ++c[p];
  }
  map<int, int> h;
  for (const auto& ci : c) {
    ++h[ci.second];
  }
  priority_queue<pair<int, int> > q;
  vector<vector<int> > s;
  for (const auto& hi : h) {
    vector<int> f(hi.first + 1, 1);
    if (hi.second > 1) poly_pow(f, hi.second);
    q.emplace(-f.size(), s.size());
    s.push_back(f);
  }
  while (q.size() > 1) {
    int u = q.top().second;
    q.pop();
    int v = q.top().second;
    q.pop();
    poly_mul(s[u], s[v]);
    q.emplace(-s[u].size(), u);
  }
  return s[q.top().second][n >> 1];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << f() << "\n";
  return 0;
}
