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;
  }
}
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];
long long cal() {
  int len = 1;
  int sum = 0;
  for (int i = 0; i <= d[ve[0]]; i++) {
    a[i] = 1;
  }
  sum += d[ve[0]];
  while (len <= sum) len <<= 1;
  for (int i = 1; i < ve.size(); i++) {
    for (int j = 0; j <= d[ve[i]]; j++) {
      b[j] = 1;
    }
    sum += d[ve[i]];
    while (len <= sum) len <<= 1;
    for (int j = d[ve[i]] + 1; j <= len; j++) b[j] = 0;
    Conv(a, b, 4);
  }
  return a[ve.size() / 2];
}
int main() {
  GetWn();
  while (~scanf("%d", &n)) {
    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;
}
