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 mod = (int)(1e9 + 7);
int tmpa[800001], tmpb[800001];
int ww[800001];
int a[18][200001];
int c[800001], f[800001];
int pa[800001], pb[800001];
int pc[800001][3];
int Inv[3][3];
const int magic[3] = {998244353};
char str[100001];
int Mod;
int mypow(int x, int y, int p) {
  int sum = 1;
  for (; y; y >>= 1) {
    if (y & 1) sum = 1LL * sum * x % p;
    x = 1LL * x * x % p;
  }
  return sum;
}
struct Unknown {
  int wn[25], P, G;
  void set(int x, int y) {
    P = x, G = y;
    for (int i = 1; i <= 23; i++) wn[i] = mypow(G, (P - 1) / (1 << i), P);
  }
  void change(int* y, int len) {
    for (int i = 1, j = len / 2; i < len - 1; i++) {
      if (i < j) swap(y[i], y[j]);
      int k = len / 2;
      for (; j >= k; j -= k, k /= 2)
        ;
      j += k;
    }
  }
  void NTT(int* y, int len, int on) {
    change(y, len);
    for (int h = 2, id = 1; h <= len; h <<= 1, ++id) {
      ww[0] = 1;
      for (int i = 1; i < (h >> 1); i++) ww[i] = 1LL * ww[i - 1] * wn[id] % P;
      for (int j = 0; j < len; j += h)
        for (int k = j; k < j + (h >> 1); k++) {
          int u = y[k], t = 1LL * y[k + (h >> 1)] * ww[k - j] % P;
          y[k] = (u + t) % P, y[k + (h >> 1)] = (u - t + P) % P;
        }
    }
    if (on == -1) {
      for (int i = 1; i < len / 2; i++) swap(y[i], y[len - i]);
      int inv = mypow(len, P - 2, P);
      for (int i = 0; i < len; i++) y[i] = 1LL * y[i] * inv % P;
    }
  }
  void mul(int* A, int* B, int len) {
    NTT(A, len, 1);
    NTT(B, len, 1);
    for (int i = 0; i < len; i++) A[i] = 1LL * A[i] * B[i] % P;
    NTT(A, len, -1);
  }
};
Unknown ntt[1];
void multiply(int* a, int* b, int len) {
  for (int j = 0; j < len; j++) pa[j] = a[j], pb[j] = b[j];
  ntt[0].mul(pa, pb, len);
  for (int i = 0; i < len; i++) a[i] = pa[i];
}
int vis[4000005];
int stk[300005];
void Prepare() {
  for (int i = 0; i < 1; i++) ntt[i].set(magic[i], 3);
}
int dfs(int l, int r, int deep, int cur) {
  if (l > r) {
    a[deep][0 + cur] = 1;
    return 1;
  }
  if (l == r) {
    int sz = 1;
    int K = vis[stk[l]];
    for (int i = 0; i <= K; i++) a[deep][i + cur] = 1;
    return K + 1;
  }
  int mid = (l + r) >> 1;
  int n1 = dfs(l, mid, deep + 1, cur);
  int n2 = dfs(mid + 1, r, deep + 1, cur + n1);
  int len = 1;
  while (len <= 2 * (n1 + n2 + 1)) len <<= 1;
  for (int i = 0; i < len; i++) tmpa[i] = tmpb[i] = 0;
  for (int i = cur; i < cur + n1; i++) tmpa[i - cur] = a[deep + 1][i];
  for (int i = cur + n1; i < cur + n1 + n2; i++)
    tmpb[i - cur - n1] = a[deep + 1][i];
  multiply(tmpa, tmpb, len);
  for (int i = cur; i < cur + n1 + n2 - 1; i++) a[deep][i] = tmpa[i - cur];
  return n1 + n2 - 1;
}
int main() {
  Prepare();
  int n, x, top = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    if (!vis[x]) {
      vis[x] = 1;
      stk[++top] = x;
    } else
      vis[x]++;
  }
  int root = dfs(1, top, 0, 0);
  printf("%d\n", a[0][n / 2]);
  return 0;
}
