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;
struct cp {
  long double x, y;
  cp(long double a = 0.0, long double b = 0.0) { x = a, y = b; }
};
inline cp operator*(cp a, cp b) {
  return cp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline cp operator+(cp a, cp b) { return cp(a.x + b.x, a.y + b.y); }
inline cp operator-(cp a, cp b) { return cp(a.x - b.x, a.y - b.y); }
const int N = 300005;
const long double pi = acos(-1.0);
const long double eps = 0.00001;
const int op[2] = {1, -1};
int to[N << 2];
cp omega[N << 2][2];
void Init(int n) {
  for (int i = 0; i < n; i++) {
    int nxt = 0;
    for (int j = 1; j <= n; j <<= 1)
      if (i & j) nxt += n / 2 / j;
    to[i] = nxt;
  }
  for (int i = 0; i < n / 2; i++)
    for (int j = 0; j < 2; j++) {
      long double ang = op[j] * i * 2.0 * pi / (long double)n;
      omega[i][j] = cp(cos(ang), sin(ang));
    }
}
void fft(cp *a, int n, int rev) {
  for (int i = 0; i < n; i++)
    if (to[i] > i) swap(a[i], a[to[i]]);
  for (int i = 1; i <= n; i <<= 1) {
    int m = i >> 1;
    for (int j = 0; j < n; j += i)
      for (int k = 0; k < m; k++) {
        int p = j + k;
        cp b0 = a[p], t = omega[n / i * k][rev] * a[m + p];
        a[p] = b0 + t;
        a[m + p] = b0 - t;
      }
  }
}
const int MOD = 998244353;
int n;
int p[N];
vector<int> v;
int cnt[N << 2];
cp *val[N << 2];
int save[N];
inline void merge(int k, int l, int r) {
  if (l == r) return;
  int x = (l + r) >> 1;
  merge(k << 1, l, x);
  merge(k << 1 | 1, x + 1, r);
  cnt[k] = cnt[k << 1] + cnt[k << 1 | 1] - 1;
  int sz = 1;
  while (sz < cnt[k]) sz <<= 1;
  for (int j = 0; j < 2; j++) {
    for (int i = 0; i < cnt[k << 1 | j]; i++)
      save[i] = val[k << 1 | j][i].x + eps;
    delete[](val[k << 1 | j]);
    val[k << 1 | j] = new cp[sz];
    for (int i = 0; i < cnt[k << 1 | j]; i++)
      val[k << 1 | j][i] = cp(1.0 * save[i], 0.0);
    for (int i = cnt[k << 1 | j]; i < sz; i++) val[k << 1 | j][i] = cp();
  }
  Init(sz);
  fft(val[k << 1], sz, 0);
  fft(val[k << 1 | 1], sz, 0);
  val[k] = new cp[sz];
  for (int i = 0; i < sz; i++) val[k][i] = val[k << 1][i] * val[k << 1 | 1][i];
  fft(val[k], sz, 1);
  for (int i = 0; i < sz; i++)
    val[k][i] =
        cp((long long)(val[k][i].x / ((long double)sz - eps)) % MOD, 0.0);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  sort(p + 1, p + n + 1);
  for (int i = 1; i <= n;) {
    int j = i;
    while (j <= n && p[i] == p[j]) j++;
    v.push_back(j - i);
    i = j;
  }
  int m = 1;
  while (m < (int)v.size()) m <<= 1;
  for (int i = 0; i < v.size(); i++) {
    cnt[m + i] = v[i] + 1;
    val[m + i] = new cp[v[i] + 1];
    for (int j = 0; j < v[i] + 1; j++) val[m + i][j] = cp(1.0, 0);
  }
  for (int i = v.size(); i < m; i++) {
    cnt[m + i] = 1;
    val[m + i] = new cp[1];
    val[m + i][0] = cp(1.0, 0);
  }
  merge(1, 0, m - 1);
  printf("%d\n", int(val[1][n / 2].x + eps));
  return 0;
}
