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;
inline int read() {
  int f = 1, x = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline long long readll() {
  long long f = 1, x = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int MAXN = 2e5 + 5, MAXM = 3e6 + 5, MOD = 998244353;
inline int mod1(int x) { return x < MOD ? x : x - MOD; }
inline int mod2(int x) { return x < 0 ? x + MOD : x; }
inline int pow_mod(int x, int i) {
  int y = 1;
  while (i) {
    if (i & 1) y = (long long)y * x % MOD;
    x = (long long)x * x % MOD;
    i >>= 1;
  }
  return y;
}
int n, c[MAXM], rev[MAXN << 2];
void ntt(vector<int> &a, int n, int flag) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int i = 1; i < n; i <<= 1) {
    int T = pow_mod(3, (MOD - 1) / (i << 1));
    if (flag == -1) T = pow_mod(T, MOD - 2);
    for (int j = 0; j < n; j += (i << 1)) {
      for (int k = 0, t = 1; k < i; ++k, t = (long long)t * T % MOD) {
        int Nx = a[j + k], Ny = (long long)t * a[i + j + k] % MOD;
        a[j + k] = mod1(Nx + Ny);
        a[i + j + k] = mod2(Nx - Ny);
      }
    }
  }
  if (flag == -1) {
    int t = pow_mod(n, MOD - 2);
    for (int i = 0; i < n; ++i) a[i] = (long long)a[i] * t % MOD;
  }
}
void cdq_fft(int l, int r, vector<int> &res) {
  if (l == r) {
    res = vector<int>(c[l + 1], 1);
    return;
  }
  int mid = (l + r) >> 1;
  vector<int> a, b;
  cdq_fft(l, mid, a);
  cdq_fft(mid + 1, r, b);
  int lim = 1, ct = 0;
  while (lim <= (int)a.size() + (int)b.size()) lim <<= 1, ct++;
  while ((int)a.size() < lim) a.push_back(0);
  while ((int)b.size() < lim) b.push_back(0);
  for (int i = 0; i < lim; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (ct - 1));
  ntt(a, lim, 1);
  ntt(b, lim, 1);
  for (int i = 0; i < lim; ++i) a[i] = (long long)a[i] * b[i] % MOD;
  ntt(a, lim, -1);
  res.resize(lim);
  for (int i = 0; i < lim; ++i) res[i] = a[i];
  while ((int)res.size() > n) res.pop_back();
  while (!res.empty() && !res.back()) res.pop_back();
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) c[read()]++;
  vector<int> tmp;
  for (int i = 2; i <= 3000000; ++i)
    if (c[i]) tmp.push_back(i);
  for (int i = 0; i < (int)tmp.size(); ++i)
    assert(tmp[i] >= i + 1), c[i + 1] = c[tmp[i]];
  vector<int> ans;
  cdq_fft(1, tmp.size(), ans);
  cout << ans[n / 2] << endl;
  return 0;
}
