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;
const long long G = 3;
const int maxn = 6e6;
int n;
int d[maxn + 10];
vector<int> ve;
long long wn[30];
long long quick_mod(long long a, long long b, long long m) {
  long long ans = 1;
  a %= m;
  while (b) {
    if (b & 1) {
      ans = ans * a % m;
      b--;
    }
    b >>= 1;
    a = a * a % m;
  }
  return ans;
}
void GetWn() {
  for (int i = 0; i < 30; i++) {
    int t = 1 << i;
    wn[i] = quick_mod(G, (mod - 1) / t, mod);
  }
}
void Rader(long long a[], int len) {
  int j = len >> 1;
  for (int i = 1; i < len - 1; i++) {
    if (i < j) swap(a[i], a[j]);
    int k = len >> 1;
    while (j >= k) {
      j -= k;
      k >>= 1;
    }
    if (j < k) j += k;
  }
}
void NTT(long long a[], int len, int on) {
  Rader(a, len);
  int id = 0;
  for (int h = 2; h <= len; h <<= 1) {
    id++;
    for (int j = 0; j < len; j += h) {
      long long w = 1;
      for (int k = j; k < j + h / 2; k++) {
        long long u = a[k] % mod;
        long long t = w * (a[k + h / 2] % mod) % mod;
        a[k] = (u + t) % mod;
        a[k + h / 2] = ((u - t) % mod + mod) % mod;
        w = w * wn[id] % mod;
      }
    }
  }
  if (on == -1) {
    for (int i = 1; i < len / 2; i++) swap(a[i], a[len - i]);
    long long Inv = quick_mod(len, mod - 2, mod);
    for (int i = 0; i < len; i++) a[i] = a[i] % mod * Inv % mod;
  }
}
long long pm(long long a, long long k, long long mod) {
  long long r = 1, t = a;
  while (k) {
    if (k & 1) r = r * t % mod;
    k >>= 1;
    t = t * t % mod;
  }
  return r;
}
void KKK(long long a[], int len, int k) {
  NTT(a, len, 1);
  for (int i = 0; i < len; i++) {
    a[i] = pm(a[i], k, mod);
  }
  NTT(a, len, -1);
}
void Conv(long long a[], long long b[], int len) {
  NTT(a, len, 1);
  NTT(b, len, 1);
  for (int i = 0; i < len; i++) a[i] = a[i] * b[i] % mod;
  NTT(a, len, -1);
}
long long a[maxn + 10], b[maxn + 10];
struct node {
  int cc;
  vector<long long> v;
  bool operator<(const node& C) const { return cc > C.cc; }
};
priority_queue<node> q;
long long cal() {
  std::vector<int> v;
  for (int i = 0; i < ve.size(); i++) {
    v.push_back(d[ve[i]]);
  }
  sort(v.begin(), v.end());
  int c = 0;
  for (int i = 0; i < v.size(); i++) {
    c++;
    if (i + 1 < v.size() && v[i + 1] == v[i]) {
      continue;
    }
    node tmp;
    tmp.cc = (v[i] + 1) * c;
    int len = 1;
    while (len <= tmp.cc) len *= 2;
    for (int j = 0; j < len; j++) tmp.v.push_back(j <= v[i] ? 1 : 0);
    KKK(&tmp.v[0], len, c);
    c = 0;
    q.push(tmp);
  }
  int sum = 0;
  while (q.size() >= 2) {
    node tmp = q.top();
    q.pop();
    node tmp1 = q.top();
    q.pop();
    sum = tmp.cc + tmp1.cc;
    int len = 1;
    while (len <= sum) len <<= 1;
    for (int i = tmp.v.size(); i <= len; i++) tmp.v.push_back(0);
    for (int i = tmp1.v.size(); i <= len; i++) tmp1.v.push_back(0);
    Conv(&tmp.v[0], &tmp1.v[0], len);
    tmp.cc = sum;
    q.push(tmp);
  }
  return q.top().v[n / 2];
}
int main() {
  GetWn();
  while (~scanf("%d", &n)) {
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    for (int i = 0; i < n; i++) {
      int x;
      scanf("%d", &x);
      d[x]++;
      ve.push_back(x);
    }
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    long long ans = cal();
    printf("%lld\n", ans % mod);
  }
  return 0;
}
