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;
inline void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while (((c = getchar()) == ' ') || c == '\n')
    ;
  x = c;
}
inline void writes(string s) { puts(s.c_str()); }
inline void writeln() { writes(""); }
inline void writei(int x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
inline void writell(long long x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
const int maxn = 262144, _g = 3, mod = 998244353;
int n, m, i, j, cnt[200005], inv[maxn + 1], w[maxn + 1], a[maxn + 1],
    b[maxn + 1], rev[maxn + 1];
vector<int> ans, all;
int pw(int x, int y) {
  int z = 1;
  while (y) {
    if (y & 1) z = 1ll * z * x % mod;
    x = 1ll * x * x % mod;
    y /= 2;
  }
  return z;
}
void init() {
  int i;
  inv[1] = 1;
  w[0] = 1;
  w[1] = pw(_g, (mod - 1) / maxn);
  for ((i) = (2); (i) <= (maxn); (i)++) {
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    w[i] = 1ll * w[i - 1] * w[1] % mod;
  }
  if (w[maxn] != 1) exit(-1);
}
int getrev(int x) {
  int len = 1, i;
  while (len <= x) len *= 2;
  for ((i) = (0); (i) <= (len - 1); (i)++) {
    rev[i] = rev[i / 2] / 2 + (i & 1) * (len / 2);
  }
  return len;
}
void ntt(int *a, int len, int op) {
  int i, j, k;
  for ((i) = (0); (i) <= (len - 1); (i)++)
    if (rev[i] < i) swap(a[i], a[rev[i]]);
  for (i = 1; i < len; i <<= 1) {
    int ys = maxn / i / 2;
    for (j = 0; j < len; j += i + i) {
      int t = (op == 1 ? 0 : maxn);
      for (k = 0; k < i; k++) {
        int x = a[j + k], y = 1ll * a[j + k + i] * w[t] % mod;
        a[j + k] = x + y;
        if (a[j + k] >= mod) a[j + k] -= mod;
        a[j + k + i] = x - y;
        if (a[j + k + i] < 0) a[j + k + i] += mod;
        t += ys * op;
      }
    }
  }
  if (op == -1) {
    for ((i) = (0); (i) <= (len - 1); (i)++) a[i] = 1ll * a[i] * inv[len] % mod;
  }
}
vector<int> mul(vector<int> va, vector<int> vb) {
  int i, len = getrev(va.size() + vb.size());
  for ((i) = (0); (i) <= (len - 1); (i)++) {
    if (i < va.size())
      a[i] = va[i];
    else
      a[i] = 0;
    if (i < vb.size())
      b[i] = vb[i];
    else
      b[i] = 0;
  }
  ntt(a, len, 1);
  ntt(b, len, 1);
  for ((i) = (0); (i) <= (len - 1); (i)++) a[i] = 1ll * a[i] * b[i] % mod;
  ntt(a, len, -1);
  vector<int> ans;
  for ((i) = (0); (i) <= (len - 1); (i)++) {
    ans.push_back(a[i]);
  }
  while (!ans.empty() && ans.back() == 0) ans.pop_back();
  return ans;
}
vector<int> solve(int l, int r) {
  if (l == r) {
    vector<int> ans;
    int i;
    for (((i)) = (1); ((i)) <= ((1 + cnt[l])); ((i))++) ans.push_back(1);
    return ans;
  }
  int mid = (l + r) / 2;
  return mul(solve(l, mid), solve(mid + 1, r));
}
int main() {
  init();
  read(n);
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    read(a[i]);
    all.push_back(a[i]);
  }
  sort((all).begin(), (all).end());
  all.resize(unique((all).begin(), (all).end()) - all.begin());
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    a[i] = upper_bound((all).begin(), (all).end(), a[i]) - all.begin();
    cnt[a[i]]++;
  }
  ans = solve(1, all.size());
  cout << ans[n / 2] << endl;
  return 0;
}
