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 N = 1100000;
const int mod = 998244353;
inline int qp(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return res;
}
int last_n = -1, rev[N];
inline void init_NTT(int n) {
  last_n = n;
  int cnt = 0;
  while ((1 << cnt) < n) cnt++;
  for (int i = 1; i < n; i++) {
    rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (cnt - 1)));
  }
}
inline void NTT(int n, int *a, int flag) {
  if (last_n != n) {
    init_NTT(n);
  }
  for (int i = 0; i < n; i++)
    if (rev[i] > i) swap(a[rev[i]], a[i]);
  for (int i = 2; i <= n; i <<= 1) {
    int w = qp(3, (mod - 1) / i);
    if (flag) w = qp(w, mod - 2);
    for (int j = 0; j < n; j += i) {
      int t = 1;
      for (int k = j; k < j + (i >> 1); k++) {
        int x = a[k], y = 1ll * a[k + (i >> 1)] * t % mod;
        a[k] = x + y;
        if (a[k] >= mod) a[k] -= mod;
        a[k + (i >> 1)] = x - y + mod;
        if (a[k + (i >> 1)] >= mod) a[k + (i >> 1)] -= mod;
        t = 1ll * t * w % mod;
      }
    }
  }
  if (flag) {
    int t = qp(n, mod - 2);
    for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * t % mod;
  }
}
inline void mult(int *a, int &n, int *b, int m) {
  int len = 1, cnt = 0;
  for (; len <= n + m - 1; len <<= 1, cnt++)
    ;
  for (int i = n; i < len; i++) a[i] = 0;
  for (int i = m; i < len; i++) b[i] = 0;
  NTT(len, a, 0);
  NTT(len, b, 0);
  for (int i = 0; i < len; i++) a[i] = 1ll * a[i] * b[i] % mod;
  NTT(len, a, 1);
  n = n + m - 1;
}
int n, p[N], c[3000005];
int m, a[N];
int pl[20][N], sz[20];
void solve(int l, int r, int d) {
  if (l == r) {
    pl[d][0] = 1;
    pl[d][a[l]] = mod - 1;
    sz[d] = a[l] + 1;
    for (int i = 1; i < sz[d] - 1; i++) pl[d][i] = 0;
    return;
  }
  int mid = (l + r) >> 1;
  solve(l, mid, d + 1);
  sz[d] = sz[d + 1];
  for (int i = 0; i < sz[d + 1]; i++) pl[d][i] = pl[d + 1][i];
  solve(mid + 1, r, d + 1);
  mult(pl[d], sz[d], pl[d + 1], sz[d + 1]);
}
int fact[N], ifact[N], inv[N];
inline int C(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return 1ll * fact[a] * ifact[b] % mod * ifact[a - b] % mod;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]), c[p[i]]++;
  for (int i = 2; i <= 3000000; i++)
    if (c[i]) a[++m] = c[i] + 1;
  sort(a + 1, a + 1 + m);
  solve(1, m, 0);
  inv[1] = 1;
  for (int i = 2; i <= n * 2; i++)
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
  fact[0] = ifact[0] = 1;
  for (int i = 1; i <= n * 2; i++) {
    fact[i] = 1ll * fact[i - 1] * i % mod;
    ifact[i] = 1ll * ifact[i - 1] * inv[i] % mod;
  }
  int ans = 0;
  for (int i = 0; i <= (n >> 1); i++) {
    ans = (ans + 1ll * pl[0][i] * C((n >> 1) + m - 1 - i, m - 1) % mod) % mod;
  }
  printf("%d\n", ans);
  return 0;
}
