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 MAXN = 6e5 + 10, MAXM = 4e6 + 10;
const int INF = INT_MAX, SINF = 0x3f3f3f3f;
const long long llINF = LLONG_MAX;
const int MOD = 998244353, mod = 998244353;
const int Lim = (1 << 19);
int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int sub(int a, int b) { return a < b ? a - b + MOD : a - b; }
int mul(int a, int b) { return (long long)a * b % MOD; }
int ksm(int base, int v) {
  int res = 1;
  while (v) {
    if (v & 1) res = mul(res, base);
    base = mul(base, base);
    v >>= 1;
  }
  return res;
}
int rev[Lim + 5], lg2[Lim + 5], rt[Lim + 5], irt[Lim + 5];
int n, k, lim, type;
void init() {
  for (int i = 2; i <= Lim; i++) lg2[i] = lg2[i >> 1] + 1;
  rt[0] = 1;
  rt[1] = ksm(3, (MOD - 1) / Lim);
  irt[0] = 1;
  irt[1] = ksm(rt[1], MOD - 2);
  for (int i = 2; i <= Lim; i++) {
    rt[i] = mul(rt[i - 1], rt[1]);
    irt[i] = mul(irt[i - 1], irt[1]);
  }
}
void NTT(vector<int> &f, int type, int lim) {
  f.resize(lim);
  int w, y, l = lg2[lim] - 1;
  for (int i = 1; i < lim; i++) {
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l);
    if (i >= rev[i]) continue;
    swap(f[i], f[rev[i]]);
  }
  l = Lim >> 1;
  for (int mid = 1; mid < lim; mid <<= 1) {
    for (int j = 0; j < lim; j += (mid << 1)) {
      for (int k = 0; k < mid; k++) {
        w = type == 1 ? rt[l * k] : irt[l * k];
        y = mul(w, f[j | k | mid]);
        f[j | k | mid] = sub(f[j | k], y);
        f[j | k] = add(f[j | k], y);
      }
    }
    l >>= 1;
  }
  if (type == 1) return;
  y = ksm(lim, MOD - 2);
  for (int i = 0; i < lim; i++) f[i] = mul(f[i], y);
}
int cnt[MAXM];
vector<int> v;
vector<int> vec[MAXM];
priority_queue<pair<int, int>, vector<pair<int, int> >,
               greater<pair<int, int> > >
    pq;
int main() {
  init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int p;
    scanf("%d", &p);
    cnt[p]++;
  }
  for (int i = 1; i <= 3e6; i++)
    if (cnt[i]) v.push_back(i);
  for (int i = 0; i < ((int)v.size()); i++) {
    cnt[v[i]] += 1;
    vec[v[i]].resize(cnt[v[i]]);
    for (int j = 0; j < cnt[v[i]]; j++) vec[v[i]][j] = 1;
    pq.push({cnt[v[i]], v[i]});
  }
  while (((int)pq.size()) > 1) {
    int u = pq.top().second;
    pq.pop();
    int v = pq.top().second;
    pq.pop();
    cnt[u] += cnt[v] - 1;
    lim = 1;
    while (lim < cnt[u]) lim <<= 1;
    NTT(vec[u], 1, lim);
    NTT(vec[v], 1, lim);
    for (int i = 0; i < lim; i++) vec[u][i] = mul(vec[u][i], vec[v][i]);
    NTT(vec[u], -1, lim);
    pq.push({cnt[u], u});
  }
  int ans = pq.top().second;
  printf("%d", vec[ans][cnt[ans] / 2]);
  return 0;
}
