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 = 200005;
const int mod = 998244353;
int n, m;
int a[maxn], cnt[maxn];
vector<int> num;
namespace Poly {
const int g = 3;
int power(int x, int pow) {
  int res = 1;
  for (; pow; pow >>= 1) {
    if (pow & 1) res = 1LL * res * x % mod;
    x = 1LL * x * x % mod;
  }
  return res;
}
void ntt(vector<int>& x, int sz, int tp) {
  for (int i = sz >> 1, j = 1; j < sz; j++) {
    if (i < j) swap(x[i], x[j]);
    int k;
    for (k = sz >> 1; i & k; i ^= k, k >>= 1)
      ;
    i ^= k;
  }
  for (int m = 2; m <= sz; m <<= 1) {
    int w;
    if (tp > 0)
      w = power(g, (mod - 1) / m);
    else
      w = power(g, mod - 1 - (mod - 1) / m);
    for (int i = 0; i < sz; i += m) {
      int cur = 1;
      for (int j = i; j < i + (m >> 1); j++) {
        int u = x[j], v = 1LL * x[j + (m >> 1)] * cur % mod;
        x[j] = u + v;
        if (x[j] >= mod) x[j] -= mod;
        x[j + (m >> 1)] = u - v;
        if (x[j + (m >> 1)] < 0) x[j + (m >> 1)] += mod;
        cur = 1LL * cur * w % mod;
      }
    }
  }
  if (tp < 0) {
    int inv = power(sz, mod - 2);
    for (int i = 0; i < (sz); i++) x[i] = 1LL * x[i] * inv % mod;
  }
}
}  // namespace Poly
vector<int> solve(int l, int r) {
  if (l == r) {
    vector<int> res;
    res.resize(cnt[l] + 1, 1);
    return res;
  }
  int mid = l + r >> 1;
  vector<int> resl = solve(l, mid);
  vector<int> resr = solve(mid + 1, r);
  int szl = int(resl.size()), szr = int(resr.size());
  int sz = 1;
  for (; sz < szl + szr - 1; sz <<= 1)
    ;
  for (int i = 0; i < (sz - szl); i++) resl.push_back(0);
  for (int i = 0; i < (sz - szr); i++) resr.push_back(0);
  Poly::ntt(resl, sz, 1);
  Poly::ntt(resr, sz, 1);
  for (int i = 0; i < (sz); i++) resl[i] = 1LL * resl[i] * resr[i] % mod;
  Poly::ntt(resl, sz, -1);
  for (int i = 0; i < (sz - (szl + szr - 1)); i++) resl.pop_back();
  return resl;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= (n); i++) {
    scanf("%d", &a[i]);
    num.push_back(a[i]);
  }
  sort(num.begin(), num.end());
  num.resize(unique(num.begin(), num.end()) - num.begin());
  m = int(num.size());
  for (int i = 1; i <= (n); i++) {
    int pos = lower_bound(num.begin(), num.end(), a[i]) - num.begin() + 1;
    cnt[pos]++;
  }
  vector<int> ans = solve(1, m);
  printf("%d\n", ans[n / 2]);
  return 0;
}
