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 P = 998244353, root = 3, MAXNUM = 1 << 23;
int bigmod(long long a, int b) {
  if (b == 0) return 1;
  return (bigmod((a * a) % P, b / 2) * (b % 2 ? a : 1ll)) % P;
}
int inv(int a, int b) {
  if (a == 1) return 1;
  return (((long long)(a - inv(b % a, a)) * b + 1) / a) % b;
}
std::vector<long long> ps(MAXNUM);
std::vector<int> rev(MAXNUM);
long long f_pow(unsigned int a, long long b) {
  long long res = 1, temp = a;
  while (b) {
    if (b & 1) res = res * temp % P;
    temp = temp * temp % P;
    b >>= 1;
  }
  return res;
}
struct poly {
  std::vector<unsigned int> co;
  int n;
  poly(int d) {
    n = d;
    co.resize(n + 1, 1);
  }
  void ntt_inv(int NN) {
    int r = 0, st, N;
    unsigned int a, b;
    while ((1 << r) < (NN >> 1)) ++r;
    for (N = 2; N <= NN; N <<= 1, --r) {
      for (st = 0; st < NN; st += N) {
        int i, ss = st + (N >> 1);
        for (i = (N >> 1) - 1; i >= 0; --i) {
          a = co[st + i];
          b = (ps[i << r] * co[ss + i]) % P;
          co[st + i] = a + b;
          if (co[st + i] >= P) co[st + i] -= P;
          co[ss + i] = a + P - b;
          if (co[ss + i] >= P) co[ss + i] -= P;
        }
      }
    }
  }
  void ntt(int NN) {
    int r = 0, st, N;
    unsigned int a, b;
    r = 0;
    for (N = NN; N > 1; N >>= 1, r++) {
      for (st = 0; st < NN; st += N) {
        int i, ss = st + (N >> 1);
        for (i = (N >> 1) - 1; i >= 0; --i) {
          a = co[st + i];
          b = co[ss + i];
          co[st + i] = a + b;
          if (co[st + i] >= P) co[st + i] -= P;
          co[ss + i] = ((a + P - b) * ps[i << r]) % P;
        }
      }
    }
  }
  poly operator*(const poly &_b) const {
    poly a = *this, b = _b;
    int k = n + b.n, i, N = 1;
    while (N <= k) N *= 2;
    a.co.resize(N, 0);
    b.co.resize(N, 0);
    int r = bigmod(root, (P - 1) / N), Ni = inv(N, P);
    ps[0] = 1;
    for (i = 1; i < N; ++i) ps[i] = (ps[i - 1] * r) % P;
    a.ntt(N);
    b.ntt(N);
    for (i = 0; i < N; ++i) a.co[i] = ((long long)a.co[i] * b.co[i]) % P;
    r = inv(r, P);
    for (i = 1; i < N / 2; ++i) std::swap(ps[i], ps[N - i]);
    a.ntt_inv(N);
    for (i = 0; i < N; ++i) a.co[i] = ((long long)a.co[i] * Ni) % P;
    a.n = n + _b.n;
    return a;
  }
};
bool operator>(const poly &a, const poly &b) { return a.n > b.n; }
int main() {
  map<int, int> m;
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int first;
    scanf("%d", &first);
    m[first]++;
  }
  priority_queue<poly, vector<poly>, greater<poly> > pq;
  for (auto it : m) {
    poly p1(it.second);
    pq.push(p1);
  }
  while (pq.size() > 1) {
    poly p1 = pq.top();
    pq.pop();
    poly p2 = pq.top();
    pq.pop();
    pq.push(p1 * p2);
  }
  printf("%d\n", pq.top().co[n / 2]);
}
