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 inf = 1e9;
const long long INF = 1e18;
const double eps = 1e-10;
const int maxn = 1e6 + 233;
const int mod = 998244353;
const int inv2 = mod + 1 >> 1;
int pow_mod(long long q, long long w) {
  int ret = 1;
  while (w) {
    if (w & 1) ret = (long long)ret * q % mod;
    q = q * q % mod;
    w >>= 1;
  }
  return ret;
}
int add(int x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
int sub(int x, int y) {
  x -= y;
  if (x < 0) x += mod;
  return x;
}
namespace Polynomial {
int c[maxn];
int rev[maxn];
int x[maxn], y[maxn];
int inv[maxn];
int f[maxn], g[maxn];
int lnb[maxn];
int getlen(int x) {
  int len = 1;
  while (len <= x) len <<= 1;
  return len;
}
void ntt(int *a, int len, int on) {
  int cnt = 0;
  while ((1 << cnt) < len) ++cnt;
  for (int i = 0; i < len; ++i) {
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (cnt - 1));
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  }
  for (int h = 1; h < len; h <<= 1) {
    int wn = pow_mod(3, (mod - 1) / (h << 1));
    for (int j = 0; j < len; j += (h << 1)) {
      int w = 1;
      for (int k = j; k < j + h; k++) {
        int u = a[k] % mod;
        int t = 1ll * w * a[k + h] % mod;
        a[k] = add(u, t);
        a[k + h] = sub(u, t);
        w = 1ll * w * wn % mod;
      }
    }
  }
  if (on == -1) {
    for (int i = 1; i < len / 2; i++) swap(a[i], a[len - i]);
    int inv = pow_mod(len, mod - 2);
    for (int i = 0; i < len; i++) a[i] = (long long)a[i] * inv % mod;
  }
}
void mul(int *a, int *b, int *c, int n, int m) {
  int len = getlen(n + m);
  for (int i = 0; i <= n; ++i) {
    x[i] = a[i];
  }
  for (int i = 0; i <= m; ++i) {
    y[i] = b[i];
  }
  ntt(x, len, 1), ntt(y, len, 1);
  for (int i = 0; i < len; ++i) {
    c[i] = (long long)x[i] * y[i] % mod;
    x[i] = y[i] = 0;
  }
  ntt(c, len, -1);
}
void inverse(int *a, int *b, int n) {
  if (n == 1) {
    b[0] = pow_mod(a[0], mod - 2);
    return;
  }
  inverse(a, b, n + 1 >> 1);
  int len = 1;
  while (len < (n << 1)) len <<= 1;
  for (int i = 0; i < n; ++i) {
    c[i] = a[i];
  }
  for (int i = n; i < len; i++) c[i] = 0;
  ntt(b, len, 1), ntt(c, len, 1);
  for (int i = 0; i < len; ++i) {
    b[i] = (2ll - 1ll * b[i] * c[i] % mod + mod) % mod * b[i] % mod;
  }
  ntt(b, len, -1);
  for (int i = n; i < len; i++) b[i] = 0;
}
void div(int *a, int *b, int *q, int *r, int n, int m) {
  memset(inv, 0, sizeof(inv));
  reverse(a, a + n + 1), reverse(b, b + m + 1);
  inverse(b, inv, getlen(n - m));
  mul(a, inv, q, n - m, n - m);
  reverse(q, q + n - m + 1);
  reverse(a, a + n + 1), reverse(b, b + m + 1);
  mul(b, q, r, m, n - m);
  for (int i = 0; i < m; ++i) {
    r[i] = sub(a[i], r[i]);
  }
}
int modsqr(int a, int n) {
  int b, k, i, x;
  if (n == 2) return a % n;
  if (pow_mod(a, (n - 1) / 2) == 1) {
    if (n % 4 == 3) {
      x = pow_mod(a, (n + 1) / 4);
    } else {
      for (b = 1; pow_mod(b, (n - 1) / 2) == 1; b++)
        ;
      i = (n - 1) / 2;
      k = 0;
      while (i % 2 == 0) {
        i /= 2, k /= 2;
        if ((1ll * pow_mod(a, i) * pow_mod(b, k) + 1) % n == 0)
          k += (n - 1) / 2;
      }
      x = 1ll * pow_mod(a, (i + 1) / 2) * pow_mod(b, k / 2) % n;
    }
    if (x * 2 > n) x = n - x;
    return x;
  }
  return -1;
}
void getsqrt(int *a, int *b, int n) {
  if (n == 1) {
    int t = modsqr((a[0] + mod) % mod, mod);
    b[0] = min(t, mod - t);
    return;
  }
  getsqrt(a, b, n + 1 >> 1);
  memset(inv, 0, sizeof(inv));
  inverse(b, inv, n);
  int len = 1;
  while (len < (n << 1)) len <<= 1;
  for (int i = 0; i < n; ++i) {
    c[i] = a[i];
  }
  for (int i = n; i < len; ++i) {
    c[i] = 0;
  }
  ntt(inv, len, 1);
  ntt(c, len, 1);
  ntt(b, len, 1);
  for (int i = 0; i < len; ++i) {
    b[i] = 1ll * inv2 * add(b[i], 1ll * inv[i] * c[i] % mod) % mod;
  }
  ntt(b, len, -1);
  for (int i = n; i < len; ++i) {
    b[i] = 0;
  }
}
void getdev(int *a, int *b, int n) {
  for (int i = 1; i < n; i++) b[i - 1] = 1ll * i * a[i] % mod;
  b[n - 1] = 0;
}
void getinvdev(int *a, int *b, int n) {
  for (int i = 1; i < n; i++) b[i] = 1ll * a[i - 1] * pow_mod(i, mod - 2) % mod;
  b[0] = 0;
}
void getln(int *a, int *b, int n) {
  getdev(a, f, n);
  inverse(a, g, n);
  int len = 1;
  while (len <= (n << 1)) len <<= 1;
  ntt(f, len, 1);
  ntt(g, len, 1);
  for (int i = 0; i < len; i++) {
    f[i] = 1ll * f[i] * g[i] % mod;
  }
  ntt(f, len, -1);
  getinvdev(f, b, len);
  for (int i = 0; i < len; i++) f[i] = g[i] = 0;
}
void getexp(int *a, int *b, int n) {
  if (n == 1) {
    b[0] = 1;
    return;
  }
  getexp(a, b, (n + 1) >> 1);
  getln(b, lnb, n);
  int len = 1;
  while (len < (n << 1)) len <<= 1;
  for (int i = 0; i < n; i++) lnb[i] = sub(a[i], lnb[i]);
  for (int i = n; i < len; i++) lnb[i] = b[i] = 0;
  lnb[0] = add(lnb[0], 1);
  ntt(lnb, len, 1);
  ntt(b, len, 1);
  for (int i = 0; i < len; i++) b[i] = 1ll * b[i] * lnb[i] % mod;
  ntt(b, len, -1);
  for (int i = n; i < len; i++) b[i] = 0;
}
}  // namespace Polynomial
using namespace Polynomial;
int n;
int a[maxn], b[maxn];
struct node {
  vector<int> v;
  bool operator<(const node &r) const { return v.size() > r.v.size(); }
};
priority_queue<node> q;
int cnt[maxn * 3];
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  for (int i = 0; i <= 3000000; i++) {
    if (!cnt[i]) continue;
    vector<int> tmp;
    for (int j = 0; j <= cnt[i]; j++) tmp.emplace_back(1);
    q.push(node{tmp});
  }
  while (1) {
    if (q.size() == 1) break;
    vector<int> t1 = q.top().v;
    q.pop();
    vector<int> t2 = q.top().v;
    q.pop();
    for (int i = 0; i < t1.size(); i++) a[i] = t1[i];
    for (int i = 0; i < t2.size(); i++) b[i] = t2[i];
    mul(a, b, c, int(t1.size()) - 1, int(t2.size()) - 1);
    vector<int> t3;
    for (int i = 0; i <= int(t1.size()) + int(t2.size()) - 2; i++)
      t3.emplace_back(c[i]);
    q.push(node{t3});
  }
  vector<int> now = q.top().v;
  q.pop();
  cout << now[int(now.size()) / 2] << '\n';
  return 0;
}
