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;
const int MOD = 998244353;
const int DIM = 1 << 19;
const int GEN = 3;
map<int, int> mmp;
vector<int> val;
int w[DIM], rev[DIM], _a[DIM], _b[DIM];
int logPow(int x, int n) {
  if (n == -1) n = MOD - 2;
  int y = 1;
  for (; n; n >>= 1) {
    if (n & 1) y = 1LL * y * x % MOD;
    x = 1LL * x * x % MOD;
  }
  return y;
}
void preNTT(int n) {
  int sz = 31 - __builtin_clz(n);
  int _w = logPow(GEN, (MOD - 1) / n);
  w[0] = w[n] = 1;
  for (int i = 1; i < n; ++i) w[i] = 1LL * w[i - 1] * _w % MOD;
  for (int i = 1; i < n; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1));
}
inline int _(int x) {
  if (x < 0) x += MOD;
  if (x >= MOD) x -= MOD;
  return x;
}
void NTT(int *a, int n, bool inv) {
  for (int i = 1; i < n; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int l = 2; l <= n; l <<= 1)
    for (int i = 0; i < n; i += l)
      for (int j = 0; j < (l >> 1); ++j) {
        int v1 = a[i + j], v2 = 1LL * a[i + j + (l >> 1)] *
                                w[inv ? n - n / l * j : n / l * j] % MOD;
        a[i + j] = _(v1 + v2);
        a[i + j + (l >> 1)] = _(v1 - v2);
      }
  if (inv) {
    int invN = logPow(n, -1);
    for (int i = 0; i < n; ++i) a[i] = 1LL * a[i] * invN % MOD;
  }
}
vector<int> multiply(vector<int> a, vector<int> b) {
  int n = a.size(), m = b.size(), sz = 1;
  while (sz <= n + m - 2) sz <<= 1;
  preNTT(sz);
  for (int i = 0; i < sz; ++i) _a[i] = i < n ? a[i] : 0;
  for (int j = 0; j < sz; ++j) _b[j] = j < m ? b[j] : 0;
  NTT(_a, sz, false);
  NTT(_b, sz, false);
  for (int i = 0; i < sz; ++i) _a[i] = 1LL * _a[i] * _b[i] % MOD;
  NTT(_a, sz, true);
  return vector<int>(_a, _a + n + m - 1);
}
vector<int> solve(int le = 0, int ri = val.size() - 1) {
  if (le == ri) return vector<int>(1 + val[le], 1);
  int md = (le + ri) >> 1;
  return multiply(solve(le, md), solve(md + 1, ri));
}
int main(void) {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    ++mmp[x];
  }
  for (auto it : mmp) val.push_back(it.second);
  cout << solve()[n / 2] << endl;
  return 0;
}
