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;
int a[200005];
int b[200005], btop;
const int MAXN = 1e7, mod = 998244353;
int add_mod(int x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
int sub_mod(int x, int y) {
  x -= y;
  if (x < 0) x += mod;
  return x;
}
long long mul_mod(long long x, int y) {
  x *= y;
  if (x >= mod) x %= mod;
  return x;
}
int pow_mod(long long x, int n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = mul_mod(res, x);
    x = mul_mod(x, x);
    n >>= 1;
  }
  return res;
}
int gl[40];
void init() {
  for (int len = 2; len <= MAXN; len <<= 1)
    gl[__builtin_ctz(len)] = pow_mod(3, (mod - 1) / len);
}
void NTT(int a[], int n, int op) {
  for (int i = 1, j = n >> 1; i < n - 1; ++i) {
    if (i < j) swap(a[i], a[j]);
    int k = n >> 1;
    while (k <= j) {
      j -= k;
      k >>= 1;
    }
    j += k;
  }
  for (int len = 2; len <= n; len <<= 1) {
    int g = gl[__builtin_ctz(len)];
    for (int i = 0; i < n; i += len) {
      int w = 1;
      for (int j = i; j < i + (len >> 1); ++j) {
        int u = a[j], t = mul_mod(a[j + (len >> 1)], w);
        a[j] = add_mod(u, t), a[j + (len >> 1)] = sub_mod(u, t);
        w = mul_mod(w, g);
      }
    }
  }
  if (op == -1) {
    reverse(a + 1, a + n);
    int inv = pow_mod(n, mod - 2);
    for (int i = 0; i < n; ++i) a[i] = mul_mod(a[i], inv);
  }
}
int A[MAXN + 5], B[MAXN + 5];
int pow2(int x) {
  int res = 1;
  while (res < x) res <<= 1;
  return res;
}
void convolution(int A[], int B[], int Asize, int Bsize) {
  int n = pow2(Asize + Bsize - 1);
  for (int i = Asize; i < n; ++i) A[i] = 0;
  for (int i = Bsize; i < n; ++i) B[i] = 0;
  NTT(A, n, 1);
  NTT(B, n, 1);
  for (int i = 0; i < n; ++i) A[i] = mul_mod(A[i], B[i]);
  NTT(A, n, -1);
  return;
}
struct PriorityQueueNode {
  vector<int> vec;
  bool operator<(const PriorityQueueNode &pqn) const {
    return vec.size() > pqn.vec.size();
  }
} pqn;
priority_queue<PriorityQueueNode> pq;
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  sort(a + 1, a + 1 + n);
  btop = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[i] != a[i - 1])
      b[++btop] = 1;
    else
      ++b[btop];
  }
  sort(b + 1, b + 1 + btop);
  for (int i = 1; i <= btop; ++i) {
    while (pqn.vec.size() < b[i] + 1) pqn.vec.push_back(1);
    pq.push(pqn);
  }
  init();
  int Asize, Bsize;
  vector<int> vec;
  while (pq.size() > 1) {
    vec = pq.top().vec;
    for (int i = 0; i < vec.size(); ++i) {
      A[i] = vec[i];
    }
    Asize = vec.size();
    pq.pop();
    vec = pq.top().vec;
    for (int i = 0; i < vec.size(); ++i) {
      B[i] = vec[i];
    }
    Bsize = vec.size();
    pq.pop();
    convolution(A, B, Asize, Bsize);
    Asize = Asize + Bsize - 1;
    vec.clear();
    vec.resize(Asize);
    for (int i = 0; i < Asize; ++i) vec[i] = A[i];
    pqn.vec = vec;
    pq.push(pqn);
  }
  vec = pq.top().vec;
  printf("%d\n", vec[vec.size() >> 1]);
  return 0;
}
