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;
struct NTT {
  vector<int> A, B, w[2], rev;
  int P = 998244353, M, G = 3;
  int Pow(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = a * 1LL * a % P)
      if (b & 1) res = res * 1LL * a % P;
    return res;
  }
  void init(int n) {
    for (M = 1; M < n; M <<= 1)
      ;
    M <<= 1;
    A.resize(M);
    B.resize(M);
    w[0].resize(M);
    w[1].resize(M);
    rev.resize(M);
    for (int i = 0; i < M; i++) {
      int x = i, &y = rev[i];
      y = 0;
      for (int k = 1; k < M; k <<= 1, x >>= 1) (y <<= 1) |= x & 1;
    }
    int x = Pow(G, (P - 1) / M), y = Pow(x, P - 2);
    w[0][0] = w[1][0] = 1;
    for (int i = 1; i < M; i++) {
      w[0][i] = w[0][i - 1] * 1LL * x % P;
      w[1][i] = w[1][i - 1] * 1LL * y % P;
    }
  }
  void ntransform(vector<int> &a, int f) {
    for (int i = 0; i < M; i++)
      if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 1; i < M; i <<= 1)
      for (int j = 0, t = M / (i << 1); j < M; j += i << 1)
        for (int k = 0, l = 0; k < i; k++, l += t) {
          int x = a[j + k + i] * 1ll * w[f][l] % P;
          int y = a[j + k];
          a[j + k + i] = y - x < 0 ? y - x + P : y - x;
          a[j + k] = y + x >= P ? y + x - P : y + x;
        }
    if (f) {
      int x = Pow(M, P - 2);
      for (int i = 0; i < M; i++) a[i] = a[i] * 1ll * x % P;
    }
  }
  void multiply(vector<int> &X, vector<int> &Y, vector<int> &res) {
    init(max(X.size(), Y.size()));
    for (int i = 0; i < M; i++) A[i] = B[i] = 0;
    for (int i = 0; i < X.size(); i++) A[i] = X[i];
    for (int i = 0; i < Y.size(); i++) B[i] = Y[i];
    ntransform(A, 0);
    ntransform(B, 0);
    res.clear();
    res.resize(M);
    for (int i = 0; i < M; i++) res[i] = A[i] * 1LL * B[i] % P;
    ntransform(res, 1);
  }
} ntt;
const int N = 2e5 + 10;
vector<int> res[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  map<int, int> M;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    M[x]++;
  }
  vector<int> f;
  for (auto it : M) f.push_back(it.second);
  priority_queue<pair<int, int>> pq;
  for (int i = 0; i < f.size(); i++) {
    res[i].assign(f[i] + 1, 1);
    pq.push({-f[i], i});
  }
  while (pq.size() > 1) {
    int x = pq.top().second;
    pq.pop();
    int y = pq.top().second;
    pq.pop();
    f[x] += f[y];
    pq.push({-f[x], x});
    ntt.multiply(res[x], res[y], res[x]);
  }
  cout << res[pq.top().second][n / 2] << endl;
  return 0;
}
