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 _G = 3, mod = 998244353, Maxn = 270000;
inline int read() {
  int X = 0;
  char ch = 0;
  while (ch < 48 || ch > 57) ch = getchar();
  while (ch >= 48 && ch <= 57) X = X * 10 + (ch ^ 48), ch = getchar();
  return X;
}
long long powM(long long a, int t = mod - 2) {
  long long ans = 1;
  while (t) {
    if (t & 1) ans = ans * a % mod;
    a = a * a % mod;
    t >>= 1;
  }
  return ans;
}
const int invG = powM(_G);
int tr[Maxn], tf;
void tpre(int n) {
  if (tf == n) return;
  tf = n;
  for (int i = 1; i < n; i++)
    tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
}
void NTT(int *g, bool op, int n) {
  tpre(n);
  static unsigned long long f[Maxn], w[Maxn] = {1};
  for (int i = 0; i < n; i++) f[i] = g[tr[i]];
  for (int l = 1; l < n; l <<= 1) {
    unsigned long long tG = powM(op ? _G : invG, (mod - 1) / (l + l));
    for (int i = 1; i < l; i++) w[i] = w[i - 1] * tG % mod;
    for (int k = 0; k < n; k += l + l)
      for (int p = 0; p < l; p++) {
        int tt = w[p] * f[k | l | p] % mod;
        f[k | l | p] = f[k | p] + mod - tt;
        f[k | p] += tt;
      }
    if (l == (1 << 10))
      for (int i = 0; i < n; i++) f[i] %= mod;
  }
  if (!op) {
    unsigned long long invn = powM(n);
    for (int i = 0; i < n; ++i) g[i] = f[i] % mod * invn % mod;
  } else
    for (int i = 0; i < n; ++i) g[i] = f[i] % mod;
}
int lim, tot, c[3005000], _s[Maxn << 1], *ts = _s;
struct Data {
  int *f, c;
} s[Maxn];
int f1[Maxn], f2[Maxn];
Data merge(Data A, Data B) {
  if (A.c * B.c < 20 * (A.c + B.c)) {
    static unsigned long long s[Maxn];
    int m = min(A.c + B.c - 1, lim);
    for (int k = 0; k < m; k++)
      for (int i = 0; i <= min(A.c - 1, k); i++)
        s[k] += 1ll * A.f[i] * B.f[k - i];
    for (int i = 0; i < m; i++) {
      A.f[i] = s[i] % mod;
      s[i] = 0;
    }
  } else {
    int m = A.c + B.c - 1, n = 1;
    while (n < m) n <<= 1;
    memcpy(f1, A.f, sizeof(int) * (A.c));
    memcpy(f2, B.f, sizeof(int) * (B.c));
    NTT(f1, 1, n);
    NTT(f2, 1, n);
    for (int i = 0; i < n; i++) f1[i] = 1ll * f1[i] * f2[i] % mod;
    NTT(f1, 0, n);
    A.c = m = min(m, lim);
    memcpy(A.f, f1, sizeof(int) * (m));
    memset(f1, 0, sizeof(int) * (n));
    memset(f2, 0, sizeof(int) * (n));
  }
  return A;
}
int main() {
  srand(0);
  lim = read();
  for (int i = 0; i < lim; i++) c[read()]++;
  for (int i = 1; i <= 3000000; i++)
    if (c[i]) {
      s[++tot].f = ts;
      ts += (s[tot].c = c[i] + 1);
    }
  for (int *i = _s; i < ts; i++) *i = 1;
  lim = lim / 2 + 1;
  while (tot > 1) {
    for (int i = 2; i <= tot; i += 2) s[i / 2] = merge(s[i - 1], s[i]);
    if (tot & 1) s[(tot + 1) / 2] = s[tot];
    tot = (tot + 1) / 2;
  }
  printf("%d", s[1].f[lim - 1]);
  return 0;
}
