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 double pi = acos(-1.0);
template <class T>
vector<T> getVectorFromArray(T ar[], int n) {
  vector<T> ret;
  ret.insert(ret.begin(), ar, ar + n);
  return ret;
}
template <class T>
vector<complex<double> > getComplexVector(vector<T> ar) {
  vector<complex<double> > ret;
  for (T x : ar) {
    ret.push_back(complex<double>(x, 0));
  }
  return ret;
}
vector<complex<double> > recursiveDFT(vector<complex<double> > ar,
                                      bool invert) {
  int n = ar.size();
  if (n == 1) {
    return ar;
  }
  vector<complex<double> > a, a0, a1;
  int m = n >> 1;
  vector<complex<double> > ar0, ar1;
  for (int i = 0; i < n;) {
    ar0.push_back(ar[i++]);
    ar1.push_back(ar[i++]);
  }
  a0 = recursiveDFT(ar0, invert);
  a1 = recursiveDFT(ar1, invert);
  a = vector<complex<double> >(n);
  double theta = (invert ? -1 : 1) * 2 * acos(-1.0) / n;
  complex<double> w, wn = complex<double>(cos(theta), sin(theta));
  w = complex<double>(1.0, 0.0);
  for (int i = 0; i < m; i++) {
    a[i] = a0[i] + w * a1[i];
    a[i + m] = a0[i] - w * a1[i];
    w = w * wn;
  }
  return a;
}
template <class T>
vector<T> dotproduct(vector<T> a, vector<T> b) {
  assert(a.size() == b.size());
  int n = a.size();
  vector<T> ret(n);
  for (int i = 0; i < n; i++) {
    ret[i] = a[i] * b[i];
  }
  return ret;
}
template <class T>
vector<T> fft(vector<T> ar, vector<T> br) {
  const int n = ar.size(), m = br.size();
  int N = max(n, m);
  int lg;
  for (lg = 0; (1 << lg) < N; lg++)
    ;
  N = 1 << (lg + 1);
  vector<complex<double> > a, b, c;
  for (int i = 0; i < N; i++) {
    a.push_back((i < n ? complex<double>(ar[i]) : complex<double>(0.0, 0.0)));
    b.push_back((i < m ? complex<double>(br[i]) : complex<double>(0.0, 0.0)));
  }
  a = recursiveDFT(a, false);
  b = recursiveDFT(b, false);
  c = dotproduct<complex<double> >(a, b);
  c = recursiveDFT(c, true);
  for (int i = 0; i < N; i++) {
    c[i] /= N;
  }
  int sz = n + m;
  vector<T> ret;
  for (int i = 0; i < sz - 1; i++) {
    ret.push_back((T)(real(c[i]) + 0.5));
  }
  return ret;
}
vector<long long int> polynomials[2 * 200009];
int ar[200009];
map<int, int> mp;
void printVect(vector<long long int> &v) {
  for (auto x : v) {
    printf(" %lld", x);
  }
  puts("");
}
int main() {
  int n, i, a;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &a);
    mp[a] = mp[a] + 1;
  }
  int mv = 0;
  int cc = 0;
  priority_queue<pair<int, int> > pq;
  pair<int, int> u, v;
  for (auto x : mp) {
    mv = max(mv, x.second);
    polynomials[++cc] = vector<long long int>(x.second + 1);
    for (int j = 0; j <= x.second; j++) polynomials[cc][j] = 1;
    pq.push(make_pair(-x.second, cc));
  }
  vector<long long int> mul;
  while (pq.size() > 1) {
    u = pq.top();
    pq.pop();
    v = pq.top();
    pq.pop();
    mul = fft(polynomials[u.second], polynomials[v.second]);
    for (i = mul.size() - 1; i > mv; i--) mul.erase(mul.end() - 1);
    for (i = 0; i < mul.size(); i++) mul[i] %= 998244353;
    polynomials[++cc] = mul;
    pq.push(make_pair(0 - ((int)mul.size()), cc));
  }
  u = pq.top();
  printf("%lld\n", polynomials[u.second][mv]);
  return 0;
}
