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 long long MOD = 998244353LL, w = 15311432LL, iw = 469870224LL;
const int K = 23;
long long W[K + 1], IW[K + 1];
void build_W() {
  W[K] = w;
  for (int k = K - 1; k >= 0; --k) W[k] = W[k + 1] * W[k + 1] % MOD;
  IW[K] = iw;
  for (int k = K - 1; k >= 0; --k) IW[k] = IW[k + 1] * IW[k + 1] % MOD;
}
long long modinv(long long a, long long mod) {
  long long r0 = a, r1 = mod;
  long long s0 = 1, s1 = 0;
  while (r1 != 0) {
    long long q = r0 / r1;
    long long r = r0 - q * r1;
    r0 = r1;
    r1 = r;
    long long s = s0 - q * s1;
    s0 = s1;
    s1 = s;
  }
  return (s0 % mod + mod) % mod;
}
long long fastpow(long long a, long long n, long long mod) {
  long long ans = 1;
  while (n) {
    if (n & 1) ans = ans * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return ans;
}
void ntt(vector<long long> &a, bool invert) {
  int n = (int)a.size();
  for (int i = 1, j = 0; i < n; ++i) {
    int bit = n >> 1;
    for (; j >= bit; bit >>= 1) j -= bit;
    j += bit;
    if (i < j) swap(a[i], a[j]);
  }
  for (int len = 2, k = 1; len <= n; len <<= 1, ++k) {
    long long wlen = (invert ? IW[k] : W[k]);
    for (int i = 0; i < n; i += len) {
      long long w = 1;
      for (int j = 0; j < len / 2; ++j) {
        long long u = a[i + j], v = a[i + j + len / 2] * w % MOD;
        a[i + j] = u + v;
        if (a[i + j] >= MOD) a[i + j] -= MOD;
        a[i + j + len / 2] = u - v;
        if (a[i + j + len / 2] < 0) a[i + j + len / 2] += MOD;
        w = w * wlen % MOD;
      }
    }
  }
  if (invert) {
    long long inv = modinv(n, MOD);
    for (int i = 0; i < n; ++i) a[i] = a[i] * inv % MOD;
  }
}
void multiply(vector<long long> &a, vector<long long> &b) {
  size_t n = 1;
  int M = max(a.size(), b.size());
  if (M <= 500) {
    int N = a.size(), M = b.size(), K = N + M - 1;
    vector<long long> c(K, 0);
    for (int i = 0; i < K; ++i) {
      for (int k = max(0, i - M + 1); k < min(i + 1, N); ++k) {
        c[i] += a[k] * b[i - k];
        c[i] %= MOD;
      }
    }
    a = c;
    return;
  }
  while (n < M) n <<= 1;
  n <<= 1;
  a.resize(n, 0), b.resize(n, 0);
  ntt(a, false), ntt(b, false);
  for (size_t i = 0; i < n; ++i) a[i] = a[i] * b[i] % MOD;
  ntt(a, true);
}
const int MAXN = 2e5;
int A[MAXN], LIM;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  build_W();
  map<int, int> M;
  int N;
  cin >> N;
  LIM = N / 2 + 1;
  for (int i = 0; i < N; ++i) {
    int p;
    cin >> p;
    ++M[p];
  }
  int K = 0;
  for (auto p : M) A[K++] = p.second;
  priority_queue<vector<long long>, vector<vector<long long>>,
                 function<bool(vector<long long> &, vector<long long> &)>>
      PQ([](vector<long long> &a, vector<long long> &b) {
        return a.size() > b.size();
      });
  for (int k = 0; k < K; ++k) PQ.emplace(A[k] + 1, 1);
  while (PQ.size() > 1) {
    vector<long long> a = PQ.top();
    PQ.pop();
    vector<long long> b = PQ.top();
    PQ.pop();
    multiply(a, b);
    if (a.size() > LIM) a.resize(LIM);
    PQ.push(a);
  }
  cout << PQ.top()[N / 2] << '\n';
  return 0;
}
