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 = 1 << 19;
const long long mod = 998244353;
long long r = 3, inv_r = (mod + 1) / r;
long long qp(long long x, long long p, long long MOD) {
  long long res = 1;
  while (p) {
    if (p & 1) res = res * x % MOD;
    x = x * x % MOD;
    p >>= 1;
  }
  return res;
}
void rader(long long *a, int len) {
  int j = len >> 1;
  for (int i = 1; i < len - 1; i++) {
    if (i < j) {
      long long t = a[i];
      a[i] = a[j];
      a[j] = t;
    }
    int k = len >> 1;
    while (k & j) {
      j ^= k;
      k >>= 1;
    }
    j ^= k;
  }
}
void NTT(long long *a, int t, int len) {
  rader(a, len);
  for (int h = 1; h < len; h <<= 1) {
    long long wn = qp((t == 1) ? r : inv_r, (mod - 1) / (h * 2), mod);
    int step = h * 2;
    for (int i = 0; i < len; i += step) {
      long long e = 1;
      for (int j = i; j < i + h; j++) {
        long long u = a[j], v = e * a[j + h] % mod;
        a[j] = (u + v) % mod;
        a[j + h] = (u - v + mod) % mod;
        e = e * wn % mod;
      }
    }
  }
  if (t == -1) {
    long long inv_len = qp(len, mod - 2, mod);
    for (int i = 0; i < len; i++) a[i] = a[i] * inv_len % mod;
  }
}
int init(int up) {
  int len = 1;
  while (len < up) len <<= 1;
  return len;
}
long long a[maxn], b[maxn], c[maxn];
int flag[3000006];
vector<long long> d[3000006];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
    q;
int main() {
  int cnt = 0;
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    if (!flag[x]) {
      flag[x] = ++cnt;
      d[flag[x]].push_back(1);
    }
    d[flag[x]].push_back(1);
  }
  for (int i = 1; i <= cnt; i++) {
    for (int j = 0; j < (int)d[i].size(); j++) printf("%lld ", d[i][j]);
    printf("\n");
  }
  for (int i = 1; i <= cnt; i++) q.push(make_pair((int)d[i].size(), i));
  while ((int)q.size() != 1) {
    int id1 = q.top().second, len1 = q.top().first;
    q.pop();
    int id2 = q.top().second, len2 = q.top().first;
    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];
    int len = init(len1 + len2);
    NTT(a, 1, len);
    NTT(b, 1, len);
    for (int i = 0; i < len; i++) c[i] = a[i] * b[i] % mod;
    NTT(c, -1, len);
    for (int i = 0; i < len + 100; i++) a[i] = 0;
    for (int i = 0; i < len + 100; i++) b[i] = 0;
    d[id1].clear();
    for (int i = 0; i < len1 + len2 - 1; i++) d[id1].push_back(c[i]);
    q.push(make_pair(len1 + len2 - 1, id1));
    for (int i = 0; i < len + 10; i++) c[i] = 0;
  }
  long long ans = q.top().second;
  printf("%lld\n", d[ans][n >> 1]);
  return 0;
}
