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 MAX = 500010;
const int MOD = 998244353;
const int G = 3;
long long modpow(long long base, long long exp) {
  base %= MOD;
  long long result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % MOD;
    base = (base * base) % MOD;
    exp >>= 1;
  }
  return result;
}
long long modinv(long long a) { return modpow(a, MOD - 2); }
void dft(vector<int>& a, int DFT, int N) {
  static int rev[MAX];
  for (int i = 0; i < N; i++) {
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (N >> 1) : 0);
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  }
  for (int m = 2, m2 = 1; m <= N; m <<= 1, m2 <<= 1) {
    int wm = modpow(G, (MOD - 1) / m * DFT + (DFT == -1 ? MOD - 1 : 0));
    for (int k = 0; k < N; k += m)
      for (int j = 0, u, t, w = 1; j < m2; j++)
        t = 1ll * w * a[k + j + m2] % MOD, u = a[k + j], w = 1ll * w * wm % MOD,
        a[k + j] = (u + t) % MOD, a[k + j + m2] = (u - t + MOD) % MOD;
  }
  if (DFT == -1)
    for (int i = 0, invN = modinv(N); i < N; i++)
      a[i] = 1ll * a[i] * invN % MOD;
}
int n;
map<int, int> c;
vector<long long> alfa;
vector<int> solve(int l, int r) {
  if (l == r) {
    vector<int> v;
    for (int i = 0; i <= alfa[l]; ++i) v.push_back(1);
    return v;
  }
  int mid = (l + r) / 2;
  vector<int> lp = solve(l, mid);
  vector<int> rp = solve(mid + 1, r);
  int len = lp.size() + rp.size();
  int N = 1;
  for (; N < len; N <<= 1)
    ;
  while ((int)lp.size() < N) lp.push_back(0);
  while ((int)rp.size() < N) rp.push_back(0);
  dft(lp, 1, N);
  dft(rp, 1, N);
  for (int i = 0; i < N; ++i) lp[i] = (1ll * lp[i] * rp[i]) % MOD;
  dft(lp, -1, N);
  while (lp.back() == 0) lp.pop_back();
  return lp;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  int p;
  for (int i = 0; i < n; ++i) {
    cin >> p;
    if (c.count(p))
      c[p]++;
    else
      c[p] = 1;
  }
  for (auto x : c) alfa.push_back(x.second);
  vector<int> ans = solve(0, alfa.size() - 1);
  cout << ans[n / 2] << endl;
  return 0;
}
