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;
void fft(vector<complex<double>>& a, bool invert) {
  int n = (int)a.size();
  if (n == 1) return;
  vector<complex<double>> a0(n / 2), a1(n / 2);
  for (int i = 0, j = 0; i < n; i += 2, ++j) {
    a0[j] = a[i];
    a1[j] = a[i + 1];
  }
  fft(a0, invert);
  fft(a1, invert);
  double ang = 2 * double(3.14159265358979323846) / n * (invert ? -1 : 1);
  complex<double> w(1), wn(cos(ang), sin(ang));
  for (int i = 0; i < n / 2; ++i) {
    a[i] = a0[i] + w * a1[i];
    a[i + n / 2] = a0[i] - w * a1[i];
    a[i] -= a[i] / complex<double>(998244353) * complex<double>(998244353);
    a[i + n / 2] -=
        a[i + n / 2] / complex<double>(998244353) * complex<double>(998244353);
    if (invert) {
      a[i] /= 2;
      a[i + n / 2] /= 2;
    }
    w *= wn;
  }
}
void multiply(const vector<uint64_t>& a, const vector<uint64_t>& b,
              vector<uint64_t>& res) {
  vector<complex<double>> fa(a.begin(), a.end());
  vector<complex<double>> fb(b.begin(), b.end());
  size_t n = 1;
  while (n < max(a.size(), b.size())) n <<= 1;
  n <<= 1;
  fa.resize(n);
  fb.resize(n);
  fft(fa, false);
  fft(fb, false);
  for (size_t i = 0; i < n; ++i) fa[i] *= fb[i];
  fft(fa, true);
  res.resize(n);
  for (size_t i = 0; i < n; ++i)
    res[i] = uint64_t(fa[i].real() + 0.5) % 998244353;
  while (res.back() == 0) {
    res.pop_back();
  }
}
vector<vector<uint64_t>> polys;
struct poly {
  int val;
  bool operator<(poly const& other) const {
    return polys[val].size() < polys[other.val].size();
  }
};
poly multiply(poly const& a, poly const& b) {
  polys.push_back({});
  multiply(polys[a.val], polys[b.val], polys.back());
  return poly{(int)polys.size() - 1};
}
int cnt[3000003];
int main() {
  int n;
  cin >> n;
  fill(cnt, cnt + 3000003, 0);
  for (int i = 0, x; i < n; ++i) {
    cin >> x;
    ++cnt[x];
    cnt[x] %= 998244353;
  }
  multiset<poly> polys_set;
  for (int i = 0; i < 3000003; ++i) {
    if (cnt[i]) {
      polys.emplace_back(cnt[i] + 1, 1);
      polys_set.insert({(int)polys.size() - 1});
    }
  }
  while (polys_set.size() > 1) {
    poly a = *polys_set.begin();
    polys_set.erase(polys_set.begin());
    poly b = *polys_set.begin();
    polys_set.erase(polys_set.begin());
    polys_set.insert(multiply(a, b));
  }
  cout << polys[polys_set.begin()->val][n / 2] << '\n';
  return 0;
}
