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 P = 998244353;
const int N = 6e5 + 10;
const int maxn = 6e5 + 10;
int fexp(int a, int n) {
  int res = 1;
  for (; n; n >>= 1, a = 1ll * a * a % P)
    if (n & 1) res = 1ll * res * a % P;
  return res;
}
struct da {
  int n, w[2][N];
  void init(int lim) {
    for (n = 1; n < lim; n <<= 1)
      ;
    w[0][0] = w[0][n] = 1;
    int g = fexp(3, (P - 1) / n);
    for (int i = 1; i < n; i++) w[0][i] = 1ll * w[0][i - 1] * g % P;
    for (int i = 0; i <= n; i++) w[1][i] = w[0][n - i];
  }
  void ntt(int *a, int v) {
    for (int i = 0, j = 0; i < n; i++) {
      if (i > j) swap(a[i], a[j]);
      for (int l = n >> 1; (j ^= l) < l; l >>= 1)
        ;
    }
    for (int l = 2; l <= n; l <<= 1) {
      int m = l >> 1;
      for (int i = 0; i < n; i += l)
        for (int k = 0; k < m; k++) {
          int t = 1ll * w[v][n / l * k] * a[i + k + m] % P;
          a[i + k + m] =
              (a[i + k] - t >= 0) ? (a[i + k] - t) : (a[i + k] - t + P);
          a[i + k] = (a[i + k] + t < P) ? (a[i + k] + t) : (a[i + k] + t - P);
        }
    }
    if (!v) return;
    int rv = fexp(n, P - 2);
    for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * rv % P;
  }
  void work(int *a, int *b, int *c, int m) {
    init(m);
    ntt(a, 0);
    ntt(b, 0);
    for (int i = 0; i < n; i++) c[i] = 1ll * a[i] * b[i] % P;
    ntt(c, 1);
  }
} NTT;
int n, lc[10000010], cnt, v[maxn], a[maxn], b[maxn], c[maxn];
vector<int> d[maxn];
priority_queue<pair<int, int>, vector<pair<int, int> >,
               greater<pair<int, int> > >
    q;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int xx = 0;
    scanf("%d", &xx);
    if (!lc[xx]) lc[xx] = ++cnt, d[cnt].push_back(1);
    d[lc[xx]].push_back(1);
  }
  for (int i = 1; i <= cnt; i++) q.push(make_pair(d[i].size(), i));
  while (q.size() != 1) {
    int id1 = q.top().second, len1 = d[id1].size();
    q.pop();
    int id2 = q.top().second, len2 = d[id2].size();
    q.pop();
    for (int i = 0; i < len1; i++) a[i] = d[id1][i];
    for (int i = 0; i < len2; i++) b[i] = d[id2][i];
    NTT.work(a, b, c, len1 + len2);
    for (int i = 0; i <= 2 * (len1 + len2) + 100; i++) a[i] = 0;
    for (int i = 0; i <= 2 * (len1 + len2) + 100; i++) b[i] = 0;
    d[id1].clear();
    for (int i = 0; i < len1 + len2; i++) d[id1].push_back(c[i]);
    q.push(make_pair(len1 + len2, id1));
    for (int i = 0; i <= 2 * (len1 + len2) + 100; i++) c[i] = 0;
  }
  int kk = q.top().second;
  int ans = 0;
  for (int i = 1; i < (int)d[kk].size(); i++) ans = max(ans, d[kk][i]);
  printf("%d\n", ans);
  return 0;
}
