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 = 262144 + 10, mo = 998244353, g = 3;
long long Pow(long long x, int p) {
  long long res = 1;
  while (p) {
    if (p & 1) (res *= x) %= mo;
    (x *= x) %= mo;
    p >>= 1;
  }
  return res;
}
long long inv(long long x) { return Pow(x, mo - 2); }
inline void FFT(int *arr, int N) {
  static int N0 = 0, rev[maxn];
  if (N != N0) {
    for (int i = 1; i < N; ++i)
      rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (N >> 1));
    N0 = N;
  }
  for (int i = 0; i < N; ++i)
    if (i < rev[i]) swap(arr[i], arr[rev[i]]);
  for (int i = 1; i < N; i <<= 1) {
    int wn = Pow(g, ((mo - 1) / i) >> 1);
    for (int j = 0; j < N; j += i << 1) {
      int w = 1;
      for (int k = 0; k < i; ++k, w = (long long)w * wn % mo) {
        int x = arr[j + k], y = (long long)w * arr[i + j + k] % mo;
        arr[j + k] = (x + y) % mo, arr[j + k + i] = (x - y + mo) % mo;
      }
    }
  }
}
inline void IDFT(int *arr, int N) {
  reverse(arr + 1, arr + N);
  FFT(arr, N);
  int invN = inv(N);
  for (int i = 0; i < N; ++i) arr[i] = (long long)arr[i] * invN % mo;
}
inline void Polynomial_Multiply(int *A, int *B, int n, int m, int *C) {
  static int tempA[maxn], tempB[maxn];
  int N = 1;
  if (n <= 100 || m <= 100) {
    N = n + m - 1;
    memset(tempA, 0, sizeof(int) * N);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        (tempA[i + j] += (long long)A[i] * B[j] % mo) %= mo;
    copy(tempA, tempA + N, C);
    return;
  }
  while (N < n + m - 1) N <<= 1;
  memcpy(tempA, A, sizeof(int) * n);
  memcpy(tempB, B, sizeof(int) * m);
  memset(tempA + n, 0, sizeof(int) * (N - n));
  memset(tempB + m, 0, sizeof(int) * (N - m));
  FFT(tempA, N);
  FFT(tempB, N);
  for (int i = 0; i < N; ++i) C[i] = (long long)tempA[i] * tempB[i] % mo;
  IDFT(C, N);
}
void Polynomial_Inverse(int *A, int *invA, int n) {
  if (n == 1) {
    invA[0] = inv(A[0]);
    return;
  }
  int mid = (n + 1) >> 1, N = 1;
  static int tempA[maxn], tempB[maxn];
  Polynomial_Inverse(A, invA, mid);
  while (N < (n << 1) - 1) N <<= 1;
  copy(A, A + n, tempA);
  memset(tempA + n, 0, sizeof(int) * (N - n));
  copy(invA, invA + mid, tempB);
  memset(tempB + mid, 0, sizeof(int) * (N - mid));
  FFT(tempA, N);
  FFT(tempB, N);
  for (int i = 0; i < N; ++i)
    invA[i] = (2 - (long long)tempA[i] * tempB[i] % mo + mo) * tempB[i] % mo;
  IDFT(invA, N);
}
void Polynomial_Division(int *A, int *B, int n, int m, int *Q, int *R) {
  if (n < m) {
    memcpy(R, A, sizeof(int) * n);
    return;
  }
  static int tempA[maxn], tempB[maxn];
  int N = 1, M = n - m + 1;
  while (N < (M << 1) - 1) N <<= 1;
  memset(tempA, 0, sizeof(int) * N);
  reverse_copy(B, B + m, tempA);
  Polynomial_Inverse(tempA, tempB, M);
  reverse_copy(A, A + n, tempA);
  Polynomial_Multiply(tempA, tempB, M, M, Q);
  reverse(Q, Q + M);
  Polynomial_Multiply(Q, B, M, m, R);
  for (int i = 0; i < m - 1; ++i)
    if ((R[i] = A[i] - R[i]) < 0) R[i] += mo;
}
int Solve(int *X, int *len, int *sum, int n, int l, int r) {
  if (n == 1) {
    for (int i = 0; i <= len[l]; i++) X[i] = 1;
    return len[l] + 1;
  }
  int mid = (l + r) >> 1;
  int llen = Solve(X, len, sum, mid - l + 1, l, mid);
  int rlen = Solve(X + sum[mid] - sum[l - 1], len, sum, r - mid, mid + 1, r);
  Polynomial_Multiply(X, X + sum[mid] - sum[l - 1], llen, rlen, X);
  return llen + rlen - 1;
}
int p[maxn];
int cnt[maxn], sum[maxn];
int X[maxn << 1];
int n, m;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  sort(p + 1, p + 1 + n);
  for (int i = 1; i <= n; i++)
    if (p[i] != p[i - 1])
      cnt[++m] = 1;
    else
      cnt[m]++;
  random_shuffle(cnt + 1, cnt + 1 + m);
  for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + cnt[i] + 1;
  Solve(X, cnt, sum, m, 1, m);
  printf("%d\n", X[n / 2]);
  return 0;
}
