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 double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const double EPS = 1e-9;
inline int qpow(int x, int y) {
  int res(1);
  while (y) {
    if (y & 1) res = 1ll * res * x % MOD;
    x = 1ll * x * x % MOD;
    y >>= 1;
  }
  return res;
}
int r[800015];
void ntt(vector<int> &x, int N, int opt) {
  register int i, j, k, m, gn, g, tmp;
  for (i = 0; i < N; ++i) {
    if (r[i] < i) {
      swap(x[i], x[r[i]]);
    }
  }
  for (m = 2; m <= N; m <<= 1) {
    k = m >> 1;
    gn = qpow(3, (MOD - 1) / m);
    for (i = 0; i < N; i += m) {
      g = 1;
      for (j = 0; j < k; ++j, g = 1ll * g * gn % MOD) {
        tmp = 1ll * x[i + j + k] * g % MOD;
        x[i + j + k] = (x[i + j] - tmp + MOD) % MOD;
        x[i + j] = (x[i + j] + tmp) % MOD;
      }
    }
  }
  if (-1 == opt) {
    reverse(x.begin() + 1, x.begin() + N);
    register int inv = qpow(N, MOD - 2);
    for (i = 0; i < N; ++i) {
      x[i] = 1ll * x[i] * inv % MOD;
    }
  }
}
int n;
map<int, int> mmp;
vector<int> x[400015];
priority_queue<pair<int, int>, vector<pair<int, int> >,
               greater<pair<int, int> > >
    que;
void print(int i) {
  for (auto y : x[i]) printf("%d ", y);
  puts("");
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    ++mmp[x];
  }
  int id = 0;
  for (auto p : mmp) {
    que.push(pair<int, int>(p.second, ++id));
    for (int i = 0; i <= p.second; ++i) {
      x[id].push_back(1);
    }
  }
  while (que.size() > 1) {
    pair<int, int> p1 = que.top();
    que.pop();
    pair<int, int> p2 = que.top();
    que.pop();
    int id1 = p1.second, id2 = p2.second;
    int n1 = p1.first + 1, n2 = p2.first + 1;
    int N = 1;
    while (N < n1 || N < n2) N <<= 1;
    N <<= 1;
    for (int i = 0; i < N; ++i) r[i] = (i & 1) * (N >> 1) + (r[i >> 1] >> 1);
    for (int i = x[id1].size(); i < N; ++i) x[id1].push_back(0);
    for (int i = x[id2].size(); i < N; ++i) x[id2].push_back(0);
    ntt(x[id1], N, 1);
    ntt(x[id2], N, 1);
    x[++id] = vector<int>(N, 0);
    for (int i = 0; i < N; ++i) x[id][i] = 1ll * x[id1][i] * x[id2][i] % MOD;
    ntt(x[id], N, -1);
    que.push(pair<int, int>(n1 + n2 - 2, id));
  }
  printf("%d\n", x[id][n / 2]);
  return 0;
}
