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 long long mod = 998244353;
int n;
vector<int> primes;
int d2i(long double d) {
  long long i = (long long)(d);
  return (d - i < i + 1 - d) ? i : (i + 1);
}
int rev[2000010];
class Polynomial {
 public:
  vector<complex<long double> > coeff;
  int degree;
  Polynomial(vector<complex<long double> > _coeff, int _degree) {
    coeff = _coeff;
    degree = _degree;
  }
  bool operator<(const Polynomial& p) const {
    return (this->degree) > (p.degree);
  }
};
priority_queue<Polynomial> q;
void get_rev(int bit) {
  for (int i = 0; i < (1 << bit); i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
void fft(vector<complex<long double> >& a, int n, int dft) {
  int bit = 0;
  while ((1 << bit) < n) ++bit;
  get_rev(bit);
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int step = 1; step < n; step <<= 1) {
    complex<long double> wn =
        exp(complex<long double>(0, dft * 3.1415926 / step));
    for (int j = 0; j < n; j += step << 1) {
      complex<long double> wnk(1, 0);
      for (int k = j; k < j + step; k++) {
        complex<long double> x = a[k];
        complex<long double> y = wnk * a[k + step];
        a[k] = x + y;
        a[k + step] = x - y;
        wnk *= wn;
      }
    }
  }
  if (dft == -1)
    for (int i = 0; i < n; i++) a[i] /= n;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int tmp;
    cin >> tmp;
    primes.push_back(tmp);
  }
  sort(primes.begin(), primes.end());
  vector<int> cnts;
  int cnt = 0;
  int p = 0;
  for (int prime : primes) {
    if (prime != p) {
      if (cnt != 0) {
        cnts.push_back(cnt);
      }
      cnt = 1;
      p = prime;
    } else {
      ++cnt;
    }
  }
  if (cnt != 0) cnts.push_back(cnt);
  for (int cnt : cnts) {
    vector<complex<long double> > coeff =
        vector<complex<long double> >(cnt + 1, complex<long double>(1, 0));
    q.push(Polynomial(coeff, cnt));
  }
  cout << "";
  while (q.size() > 1) {
    Polynomial p1 = q.top();
    q.pop();
    Polynomial p2 = q.top();
    q.pop();
    int d1 = p1.degree;
    int d2 = p2.degree;
    int d = d1 + d2;
    int s = 1;
    while (s < d + 1) s <<= 1;
    d = s - 1;
    auto coeff1 = p1.coeff;
    auto coeff2 = p2.coeff;
    while (coeff1.size() < d + 1) {
      coeff1.push_back(complex<long double>(0, 0));
    }
    while (coeff2.size() < d + 1) {
      coeff2.push_back(complex<long double>(0, 0));
    }
    fft(coeff1, d + 1, 1);
    fft(coeff2, d + 1, 1);
    vector<complex<long double> > co =
        vector<complex<long double> >(d + 1, complex<long double>(0, 0));
    for (int i = 0; i < d + 1; ++i) {
      co[i] = coeff1[i] * coeff2[i];
    }
    fft(co, d + 1, -1);
    for (int i = 0; i < d + 1; ++i) {
      co[i] = complex<long double>(d2i(co[i].real()) % mod,
                                   d2i(co[i].imag()) % mod);
    }
    q.push(Polynomial(co, d));
  }
  Polynomial po = q.top();
  cout << d2i(po.coeff[n / 2].real()) % mod << endl;
  return 0;
}
