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;
#pragma GCC diagnostic ignored "-Wmissing-declarations"
inline int safe_mul(const int x, const int y)
    __attribute__((warn_unused_result));
int const mod = 998244353;
inline int safe_mul(const int x, const int y) {
  return x * static_cast<long long>(y) % mod;
}
inline void safe_add(int& x, const int y) {
  x += y;
  if (x >= mod) x -= mod;
}
inline int safe_pow(int x, int y) {
  int res = 1;
  for (; y > 0; y >>= 1) {
    if (y & 1) res = safe_mul(x, res);
    x = safe_mul(x, x);
  }
  return res;
}
const int root_pw = 1 << 21;
int root;
int root_1;
void fft(vector<int>& a, bool invert) {
  int n = (int)a.size();
  for (int i = 1, j = 0; i < n; ++i) {
    int bit = n >> 1;
    for (; j >= bit; bit >>= 1) j -= bit;
    j += bit;
    if (i < j) swap(a[i], a[j]);
  }
  for (int len = 2; len <= n; len <<= 1) {
    int wlen = invert ? root_1 : root;
    for (int i = len; i < root_pw; i <<= 1) wlen = safe_mul(wlen, wlen);
    for (int i = 0; i < n; i += len) {
      int w = 1;
      for (int j = 0; j < len / 2; ++j) {
        int u = a[i + j], v = safe_mul(a[i + j + len / 2], w);
        a[i + j] = u + v < mod ? u + v : u + v - mod;
        a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + mod;
        w = safe_mul(w, wlen);
      }
    }
  }
  if (invert) {
    int nrev = safe_pow(n, mod - 2);
    for (int i = 0; i < n; ++i) a[i] = safe_mul(a[i], nrev);
  }
}
int need;
vector<int> multiply(vector<int> a, vector<int> b) {
  size_t n = 1;
  while (n < max(a.size(), b.size())) n <<= 1;
  n <<= 1;
  a.resize(n, 0), b.resize(n, 0);
  fft(a, false), fft(b, false);
  for (size_t i = 0; i < n; ++i) a[i] = safe_mul(a[i], b[i]);
  fft(a, true);
  while (!a.empty() && (a.back() == 0 || a.size() > need + 1)) a.pop_back();
  return a;
}
int solve(map<int, int> primes) {
  auto comp = [](const vector<int>& l, const vector<int>& r) {
    return l.size() < r.size();
  };
  multiset<vector<int>, decltype(comp)> polys(comp);
  for (auto pa : primes) polys.insert(vector<int>(pa.second + 1, 1));
  while (polys.size() > 1) {
    auto vec = multiply(*polys.begin(), *next(polys.begin()));
    polys.erase(polys.begin());
    polys.erase(polys.begin());
    polys.insert(move(vec));
  }
  return polys.begin()->operator[](need);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  for (int i = 1; i < mod; ++i) {
    if (safe_pow(i, root_pw) == 1 && safe_pow(i, root_pw >> 1) != 1) {
      root = i;
      root_1 = safe_pow(root, mod - 2);
      break;
    }
  }
  int n;
  cin >> n;
  need = n / 2;
  map<int, int> cnt;
  while (n--) {
    int p;
    cin >> p;
    ++cnt[p];
  }
  cout << solve(cnt) << endl;
}
