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 P = 998244353;
const int N = 3e5 + 100;
inline int pow_mod(int x, int k) {
  int res = 1, base = x;
  while (k) {
    if (k & 1) res = 1LL * res * base % P;
    k >>= 1;
    base = 1LL * base * base % P;
  }
  return res;
}
int omg[2][N];
int n;
int a[N];
int num;
inline int add(int x, int y) {
  x += y;
  if (x >= P) x -= P;
  return x;
}
struct polynomial {
  int siz;
  vector<int> v1;
  polynomial() {
    v1.resize(0);
    siz = 0;
  }
};
queue<polynomial> q1;
struct FFT {
  void init() {
    omg[0][0] = 1;
    omg[1][0] = 1;
    int o1 = pow_mod(3, (P - 1) / num);
    for (int i = 1; i <= num - 1; ++i) {
      omg[0][i] = 1LL * omg[0][i - 1] * o1 % P;
      omg[1][i] = 1LL * omg[1][i - 1] * pow_mod(o1, P - 2) % P;
    }
  }
  void fft(int siz, polynomial &a, int id) {
    int len = 0;
    while ((1 << len) < siz) ++len;
    for (int i = 0; i <= siz - 1; ++i) {
      int t = 0;
      for (int j = 0; j <= len - 1; ++j) {
        if ((i >> j) & 1) t |= 1 << (len - j - 1);
      }
      if (i < t) swap(a.v1[i], a.v1[t]);
    }
    for (int l = 2, m = 1; l <= siz; l *= 2, m *= 2) {
      for (int b = 0; b < siz; b += l) {
        for (int j = 0; j <= m - 1; ++j) {
          int w = 1LL * omg[(-id + 1) / 2][num / l * j] * a.v1[b + j + m] % P;
          a.v1[b + j + m] = add(a.v1[b + j] - w, P);
          a.v1[b + j] = add(a.v1[b + j], w);
        }
      }
    }
    if (id == -1) {
      int z = pow_mod(siz, P - 2);
      for (int i = 0; i <= siz - 1; ++i) a.v1[i] = 1LL * a.v1[i] * z % P;
    }
  }
  void mul(polynomial &a, polynomial &b) {
    int c = a.v1.size();
    while (a.siz + b.siz >= c) {
      c *= 2;
    }
    a.siz = a.siz + b.siz;
    while ((int)a.v1.size() < c) a.v1.push_back(0);
    while ((int)b.v1.size() < c) b.v1.push_back(0);
    fft(a.v1.size(), a, 1);
    fft(b.v1.size(), b, 1);
    for (int i = 0; i <= c - 1; ++i) a.v1[i] = 1LL * a.v1[i] * b.v1[i] % P;
    fft(a.v1.size(), a, -1);
  }
} f;
map<int, int> ct;
polynomial a1, a2, z;
int main() {
  scanf("%d", &n);
  num = 1;
  while (num <= n) num *= 2;
  f.init();
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    ++ct[a[i]];
  }
  int w = 0;
  for (int i = 1; i <= n; ++i) {
    int z = a[i];
    if (ct[a[i]] > 0) {
      a[++w] = ct[z];
      ct[z] = 0;
    }
  }
  for (int i = 1; i <= w; ++i) {
    z = polynomial();
    for (int j = 0; j <= a[i]; ++j) z.v1.push_back(1);
    int cz = 1;
    while (cz <= (int)z.v1.size()) cz *= 2;
    while ((int)z.v1.size() < cz) z.v1.push_back(0);
    z.siz = a[i];
    q1.push(z);
  }
  while (q1.size() > 1) {
    a1 = q1.front();
    q1.pop();
    a2 = q1.front();
    q1.pop();
    f.mul(a1, a2);
    q1.push(a1);
  }
  printf("%d\n", q1.front().v1[ceil(n / 2.0)]);
  return 0;
}
