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 maxn = 3e6 + 14, mod = 1e9 + 7;
namespace FFT {
const long long MAX = 1 << 21;
const double PII = acos(-1);
long long N;
complex<double> omega[MAX];
complex<double> a1[MAX], a2[MAX];
complex<double> z1[MAX], z2[MAX];
void fft(complex<double> *a, complex<double> *z, long long m = N) {
  if (m == 1) {
    z[0] = a[0];
  } else {
    long long s = N / m;
    m /= 2;
    fft(a, z, m);
    fft(a + s, z + m, m);
    for (long long i = 0; i < (m); i++) {
      complex<double> c = omega[s * i] * z[m + i];
      z[m + i] = z[i] - c;
      z[i] += c;
    }
  }
}
void mult(long long *a, long long *b, long long *c, long long len) {
  N = 2 * len;
  while (N & (N - 1)) ++N;
  assert(N <= MAX);
  for (long long i = 0; i < (N); i++) a1[i] = 0;
  for (long long i = 0; i < (N); i++) a2[i] = 0;
  for (long long i = 0; i < (len); i++) a1[i] = a[i];
  for (long long i = 0; i < (len); i++) a2[i] = b[i];
  for (long long i = 0; i < (N); i++) omega[i] = polar(1.0, 2 * PII / N * i);
  fft(a1, z1, N);
  fft(a2, z2, N);
  for (long long i = 0; i < (N); i++)
    omega[i] = complex<double>(1, 0) / omega[i];
  for (long long i = 0; i < (N); i++)
    a1[i] = z1[i] * z2[i] / complex<double>(N, 0);
  fft(a1, z1, N);
  for (long long i = 0; i < (2 * len); i++) c[i] = round(z1[i].real()) + 0.5;
}
void mult_mod(long long *a, long long *b, long long *c, long long len,
              long long mod) {
  static long long a0[MAX], a1[MAX];
  static long long b0[MAX], b1[MAX];
  static long long c0[MAX], c1[MAX], c2[MAX];
  for (long long i = 0; i < (len); i++) a0[i] = a[i] & 0xFFFF;
  for (long long i = 0; i < (len); i++) a1[i] = a[i] >> 16;
  for (long long i = 0; i < (len); i++) b0[i] = b[i] & 0xFFFF;
  for (long long i = 0; i < (len); i++) b1[i] = b[i] >> 16;
  FFT::mult(a0, b0, c0, len);
  FFT::mult(a1, b1, c2, len);
  for (long long i = 0; i < (len); i++) (a0[i] += a1[i]) %= mod;
  for (long long i = 0; i < (len); i++) (b0[i] += b1[i]) %= mod;
  FFT::mult(a0, b0, c1, len);
  for (long long i = 0; i < (2 * len); i++)
    c1[i] = ((long long)c1[i] - c0[i] - c2[i] + 2 * mod) % mod;
  for (long long i = 0; i < (2 * len); i++) c1[i] %= mod;
  for (long long i = 0; i < (2 * len); i++) c2[i] %= mod;
  for (long long i = 0; i < (2 * len); i++)
    c[i] = (c0[i] + ((long long)c1[i] << 16) + ((long long)c2[i] << 32)) % mod;
}
}  // namespace FFT
map<long long, long long> cnt;
long long n, a[maxn];
vector<long long> solve(long long l, long long r) {
  if (r - l == 1) return vector<long long>(a[l] + 1, 1);
  long long mid = (l + r) / 2;
  vector<long long> L = solve(l, mid), R = solve(mid, r);
  long long real = L.size() + R.size() - 1;
  vector<long long> ret(max(L.size(), R.size()) * 2);
  if (L.size() < R.size())
    L.resize(R.size());
  else
    R.resize(L.size());
  FFT::mult_mod(L.data(), R.data(), ret.data(), L.size(), mod);
  ret.resize(real);
  return ret;
}
void shuffle(long long l = 0, long long r = n) {
  if (r - l < 2) return;
  vector<long long> L, R;
  for (long long i = 0; i < r - l; i++) (i & 1 ? L : R).push_back(a[l + i]);
  for (long long i = 0; i < r - l; i++)
    a[l + i] = i < L.size() ? L[i] : R[i - L.size()];
  long long mid = (l + r) / 2;
  shuffle(l, mid);
  shuffle(mid, r);
}
int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (long long i = 0; i < n; i++) {
    long long x;
    cin >> x;
    cnt[x]++;
  }
  n = cnt.size();
  auto it = cnt.begin();
  for (long long i = 0; i < n; i++) a[i] = it++->second;
  vector<long long> ans = solve(0, n);
  cout << ans[ans.size() / 2] << '\n';
}
