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;
template <typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
  return a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
  return a < b ? a : b;
}
const char lf = '\n';
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline int ty() {
  int a = 0;
  int b = 1, c = fetch();
  while (!isdigit(c)) b ^= c == '-', c = fetch();
  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
  return b ? a : -a;
}
}  // namespace ae86
using ae86::ty;
const int _ = 533333, __ = 3000007, mo = 998244353, gmo = 3, igmo = 332748118;
template <typename T1, typename T2>
inline T1 ad(T1 &a, T2 b) {
  return a = a + b >= mo ? a + b - mo : a + b;
}
template <typename T1, typename T2>
inline T1 dl(T1 &a, T2 b) {
  return a = a >= b ? a - b : a - b + mo;
}
template <typename T1, typename T2>
inline T1 add(T1 a, T2 b) {
  return a + b >= mo ? a + b - mo : a + b;
}
template <typename T1, typename T2>
inline T1 del(T1 a, T2 b) {
  return a >= b ? a - b : a - b + mo;
}
long long powa(long long a, long long t) {
  long long b = 1;
  while (t) {
    if (t & 1) b = b * a % mo;
    a = a * a % mo, t >>= 1;
  }
  return b;
}
inline long long inva(long long a) { return powa(a, mo - 2); }
int rev[_];
int nttmake(int n) {
  int nn = 1, lg = 0;
  while (nn < n) nn <<= 1, lg++;
  rev[0] = 0;
  for (int i = 1; i < nn; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  return nn;
}
void ntt(long long a[], int nn, int dir) {
  for (int i = 0; i < nn; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int i = 1; i < nn; i <<= 1)
    for (int j = 0, g = powa(dir > 0 ? gmo : igmo, (mo - 1) / (i + i)); j < nn;
         j += i + i)
      for (int k = 0, ig = 1, x, y; k < i; k++, ig = 1ll * ig * g % mo)
        x = a[j + k], y = a[j + k + i] * ig % mo, a[j + k] = add(x, y),
        a[j + k + i] = del(x, y);
  if (dir < 0)
    for (int i = 0, x = inva(nn); i < nn; i++) a[i] = a[i] * x % mo;
}
vector<long long> operator*(vector<long long> a, vector<long long> b) {
  static long long pa[_], pb[_];
  int la = ((int)((a).size())), lb = ((int)((b).size())),
      nn = nttmake(la + lb - 1);
  for (int i = 0; i < la; i++) pa[i] = a[i];
  for (int i = la; i < nn; i++) pa[i] = 0;
  for (int i = 0; i < lb; i++) pb[i] = b[i];
  for (int i = lb; i < nn; i++) pb[i] = 0;
  ntt(pa, nn, 1), ntt(pb, nn, 1);
  for (int i = 0; i < nn; i++) pa[i] = pa[i] * pb[i] % mo;
  ntt(pa, nn, -1);
  vector<long long> c(la + lb - 1);
  for (int i = 0; i < ((int)((c).size())); i++) c[i] = pa[i];
  return c;
}
int m = 0;
vector<long long> ma[_];
vector<long long> dfs(int l, int r) {
  if (l == r) return ma[l];
  int mid = (l + r) >> 1;
  return dfs(l, mid) * dfs(mid + 1, r);
}
int n, val[_] = {0}, cnt[__] = {0};
int main() {
  ios::sync_with_stdio(0), cout.tie(nullptr);
  n = ty();
  for (int i = 1; i <= n; i++) val[i] = ty();
  for (int i = 1; i <= n; i++) cnt[val[i]]++;
  for (int i = 1; i <= n; i++)
    if (cnt[val[i]])
      ma[++m] = vector<long long>(cnt[val[i]] + 1, 1), cnt[val[i]] = 0;
  vector<long long> res = dfs(1, m);
  cout << res[((int)((res).size())) / 2] << lf;
  return 0;
}
