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 maxt = (1 << 20);
int pow2, c2;
int n;
inline int quickpow(int base, int ind) {
  int ans = 1;
  while (ind > 0) {
    if (ind & 1) ans = ans * 1ll * base % 998244353;
    ind >>= 1;
    base = base * 1ll * base % 998244353;
  }
  return ans;
}
int r[maxt];
inline void init(int mxlen) {
  mxlen = min(mxlen, (n / 2) + 1);
  pow2 = 1;
  c2 = 0;
  while (pow2 <= mxlen) pow2 <<= 1, c2++;
  for (int i = 0; i < pow2; i++)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (c2 - 1));
}
int pw3[22][maxt];
inline void fft(vector<int> &a, int op) {
  for (int i = 0; i < pow2; i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int j = 1, cj = 1; j < pow2; j <<= 1, cj++) {
    for (int k = 0; k < pow2; k += (j << 1)) {
      for (int l = 0; l < j; l++) {
        int nx = a[k + l], ny = pw3[cj][l] * 1ll * a[k + j + l] % 998244353;
        a[k + l] = (nx + ny) % 998244353;
        a[k + j + l] = (nx - ny + 998244353) % 998244353;
      }
    }
  }
}
const int maxm = 2e5 + 10;
int num[maxm], cnt[maxm], qkinv[22];
vector<int> res[maxt];
inline void divd(int l, int r, int x) {
  if (l == r) {
    res[x].resize(cnt[l] + 1);
    for (int i = 0; i < cnt[l] + 1; i++) res[x][i] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  divd(l, mid, x * 2);
  divd(mid + 1, r, x * 2 + 1);
  init(res[x * 2].size() + res[x * 2 + 1].size() - 1);
  int nwsize = pow2;
  while (res[x * 2].size() < nwsize) res[x * 2].push_back(0);
  res[x * 2].resize(pow2);
  while (res[x * 2 + 1].size() < nwsize) res[x * 2 + 1].push_back(0);
  res[x * 2 + 1].resize(pow2);
  fft(res[x * 2], 1);
  fft(res[x * 2 + 1], 1);
  res[x].resize(pow2);
  for (int i = 0; i < pow2; i++)
    res[x][i] = res[x * 2][i] * 1ll * res[x * 2 + 1][i] % 998244353;
  fft(res[x], 1);
  reverse(res[x].begin() + 1, res[x].end());
  int rn = qkinv[c2];
  for (int i = 0; i < pow2; i++) res[x][i] = res[x][i] * 1ll * rn % 998244353;
  res[x * 2].clear();
  res[x * 2 + 1].clear();
  return;
}
vector<int> od, lsh;
inline bool less2(int a, int b) { return cnt[a] < cnt[b]; }
int main() {
  for (int i = 1; i < 22; i++) {
    int gen = quickpow(3, (998244353 - 1) / (1 << i));
    pw3[i][0] = 1;
    for (int j = 1; j < (1 << i) && j < maxt; j++)
      pw3[i][j] = pw3[i][j - 1] * 1ll * gen % 998244353;
  }
  for (int i = 0; i < 22; i++) {
    qkinv[i] = quickpow(1 << i, 998244353 - 2);
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &num[i]);
    lsh.push_back(num[i]);
  }
  sort(lsh.begin(), lsh.end());
  lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
  for (int i = 0; i < n; i++) {
    num[i] = lower_bound(lsh.begin(), lsh.end(), num[i]) - lsh.begin();
    cnt[num[i]]++;
  }
  od.resize(lsh.size());
  for (int i = 0; i < od.size(); i++) od[i] = i;
  sort(od.begin(), od.end(), less2);
  divd(0, od.size() - 1, 1);
  printf("%d\n", res[1][n / 2]);
  return 0;
}
