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 maxn = 4e5 + 5;
int fact[maxn];
int invf[maxn];
int po(int a, int b) {
  if (b == 0) return 1;
  if (b == 1) return a;
  if (b % 2 == 0) {
    int u = po(a, b / 2);
    return (u * u) % p;
  } else {
    int u = po(a, b - 1);
    return (a * u) % p;
  }
}
int inv(int x) { return po(x, p - 2); }
int c(int n, int k) {
  int ans = fact[n];
  ans *= invf[k];
  ans %= p;
  ans *= invf[n - k];
  ans %= p;
  return ans;
}
const double pi = 3.14159265358979323;
vector<complex<double> > fft(vector<complex<double> > a) {
  int n = a.size();
  if (n == 1) {
    vector<complex<double> > ans(1);
    ans[0] = a[0];
    return ans;
  }
  vector<complex<double> > a0, a1;
  for (int i = 0; i < n; ++i) {
    if (i % 2 == 0)
      a0.push_back(a[i]);
    else
      a1.push_back(a[i]);
  }
  vector<complex<double> > ans0 = fft(a0);
  vector<complex<double> > ans1 = fft(a1);
  vector<complex<double> > ans(n);
  vector<complex<double> > u;
  for (int i = 0; i < n; ++i) {
    complex<double> w;
    if (i < (n / 2)) {
      w = complex<double>(cos(2 * pi * i / n), sin(2 * pi * i / n));
      u.push_back(w);
    } else {
      w = (-u[i - (n / 2)]);
    }
    if (i < (n / 2))
      ans[i] = ans0[i] + w * ans1[i];
    else
      ans[i] = ans0[i - (n / 2)] + w * ans1[i - (n / 2)];
  }
  return ans;
}
vector<complex<double> > dft(vector<complex<double> > a) {
  int n = a.size();
  vector<complex<double> > v = fft(a);
  for (int i = 0; i < n; ++i) {
    v[i] /= n;
  }
  reverse(v.begin() + 1, v.end());
  return v;
}
vector<complex<double> > mul1(vector<complex<double> > a,
                              vector<complex<double> > b) {
  vector<complex<double> > a1 = fft(a);
  vector<complex<double> > b1 = fft(b);
  for (int i = 0; i < a.size(); ++i) a1[i] *= b1[i];
  vector<complex<double> > v = dft(a1);
  return v;
}
vector<int> mul0(vector<int> a, vector<int> b) {
  int sz = a.size() + b.size() - 1;
  int u;
  for (int i = 1; i < sz; i *= 2) {
    u = (2 * i);
  }
  if (sz == 1) u = 2;
  while (a.size() < u) a.push_back(0);
  while (b.size() < u) b.push_back(0);
  vector<complex<double> > a1, b1;
  for (int i = 0; i < a.size(); ++i) {
    a1.push_back(complex<double>(a[i], 0));
    b1.push_back(complex<double>(b[i], 0));
  }
  vector<complex<double> > res1 = mul1(a1, b1);
  vector<int> res;
  for (int i = 0; i < sz; ++i) {
    res.push_back((int)(res1[i].real() + 0.5));
  }
  return res;
}
vector<int> mul1(vector<vector<int> > z) {
  int sz = z.size();
  if (sz == 1) return z[0];
  if (sz == 2) {
    return mul0(z[0], z[1]);
  }
  vector<vector<int> > z1, z2;
  for (int i = 0; i < sz / 2; ++i) z1.push_back(z[i]);
  for (int i = sz / 2; i < sz; ++i) z2.push_back(z[i]);
  vector<int> ans1, ans2;
  ans1 = mul1(z1);
  ans2 = mul1(z2);
  return mul0(ans1, ans2);
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int u1 = 1;
  for (int i = 0; i < maxn; ++i) {
    fact[i] = u1;
    invf[i] = inv(fact[i]);
    u1 *= (i + 1);
    u1 %= p;
  }
  int n;
  cin >> n;
  int a[n];
  map<int, int> u;
  vector<int> keys;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (u.count(a[i]))
      u[a[i]]++;
    else {
      keys.push_back(a[i]);
      u[a[i]] = 1;
    }
  }
  vector<int> v;
  for (auto h : keys) {
    v.push_back(u[h]);
  }
  vector<vector<int> > z;
  for (auto h : keys) {
    int sz = u[h];
    vector<int> g;
    for (int i = 0; i <= sz; ++i) {
      g.push_back(1);
    }
    z.push_back(g);
  }
  vector<int> o = mul1(z);
  cout << (o[n / 2] % p + p) % p;
  return 0;
}
