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 std::vector;
const int N = 1 << 21, mu = 998244353, Inv = (mu + 1) / 3;
vector<vector<int> > v;
int r[N], l, lim, a[3000005], n, x;
int ksm(int x, int y) {
  int ans = 1;
  for (; y; y >>= 1, x = (long long)x * x % mu)
    if (y & 1) ans = (long long)ans * x % mu;
  return ans;
}
void init(int n) {
  l = 0, lim = 1;
  while (lim < n) lim <<= 1, l++;
  for (int i = 0; i < lim; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
void fft(vector<int> &a, int flag) {
  a.resize(lim);
  for (int i = 0; i < lim; i++)
    if (i < r[i]) std::swap(a[i], a[r[i]]);
  for (int mid = 1; mid < lim; mid <<= 1) {
    int w = ksm(flag == 1 ? 3 : Inv, (mu - 1) / (mid << 1));
    for (int j = 0; j < lim; j += (mid << 1)) {
      for (int k = 0, ww = 1; k < mid; k++, ww = (long long)ww * w % mu) {
        int x = a[j + k], y = (long long)ww * a[j + mid + k] % mu;
        a[j + k] = (x + y) % mu;
        a[j + mid + k] = (x + mu - y) % mu;
      }
    }
  }
  if (flag == -1) {
    int inv = ksm(lim, mu - 2);
    for (int i = 0; i < lim; i++) a[i] = (long long)a[i] * inv % mu;
  }
}
vector<int> solve(int L, int R) {
  if (L == R) return v[L];
  int mid = (L + R) >> 1;
  vector<int> pl = solve(L, mid), pr = solve(mid + 1, R);
  int len = pl.size() + pr.size();
  init(len), fft(pl, 1), fft(pr, 1);
  for (int i = 0; i < lim; i++) pl[i] = (long long)pl[i] * pr[i] % mu;
  fft(pl, -1);
  pl.resize(len);
  return pl;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    a[x]++;
  }
  for (int i = 2; i <= 3000000; i++) {
    if (!a[i]) continue;
    vector<int> t(a[i] + 1);
    for (int j = 0; j <= a[i]; j++) t[j] = 1;
    v.push_back(t);
  }
  printf("%d ", solve(0, v.size() - 1)[(n + 1) / 2]);
}
