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 C = 26;
const int MOD = 998244353;
inline int mod_add(int a, int b, int m = MOD) {
  int sum = a + b;
  return sum >= m ? sum - m : sum;
}
inline int mod_sub(int a, int b, int m = MOD) {
  int diff = a - b;
  return diff < 0 ? diff + m : diff;
}
inline int mod_mul(int a, int b, int m = MOD) {
  return (uint64_t)a * b % m;
  uint64_t x = (uint64_t)a * b;
  unsigned x_high = x >> 32, x_low = (unsigned)x;
  unsigned quot, rem;
  asm("divl %4; \n\t"
      : "=a"(quot), "=d"(rem)
      : "d"(x_high), "a"(x_low), "r"(m));
  return rem;
}
inline int mod_inv(int a, int m = MOD) {
  int g = m, r = a, x = 0, y = 1;
  while (r != 0) {
    int q = g / r;
    g %= r;
    swap(g, r);
    x -= q * y;
    swap(x, y);
  }
  assert(g == 1);
  assert(y == m || y == -m);
  return x < 0 ? x + m : x;
}
inline int mod_pow(int a, long long p, int m = MOD) {
  assert(p >= 0);
  int result = 1;
  while (p > 0) {
    if (p & 1) result = mod_mul(result, a, m);
    a = mod_mul(a, a, m);
    p >>= 1;
  }
  return result;
}
namespace NTT {
vector<int> roots = {0, 1};
vector<int> bit_reverse;
int max_size = -1;
int root;
bool is_power_of_two(int n) { return (n & (n - 1)) == 0; }
int round_up_power_two(int n) {
  assert(n > 0);
  while (n & (n - 1)) n = (n | (n - 1)) + 1;
  return n;
}
int get_length(int n) {
  assert(is_power_of_two(n));
  return __builtin_ctz(n);
}
void bit_reorder(int n, vector<int> &values) {
  if ((int)bit_reverse.size() != n) {
    bit_reverse.assign(n, 0);
    int length = get_length(n);
    for (int i = 0; i < n; i++)
      bit_reverse[i] = (bit_reverse[i >> 1] >> 1) + ((i & 1) << (length - 1));
  }
  for (int i = 0; i < n; i++)
    if (i < bit_reverse[i]) swap(values[i], values[bit_reverse[i]]);
}
void find_root() {
  int order = MOD - 1;
  max_size = 1;
  while (order % 2 == 0) {
    order /= 2;
    max_size *= 2;
  }
  root = 2;
  while (!(mod_pow(root, max_size) == 1 && mod_pow(root, max_size / 2) != 1))
    root++;
}
void prepare_roots(int n) {
  if (max_size < 0) find_root();
  if ((int)roots.size() >= n) return;
  int length = get_length(roots.size());
  roots.resize(n);
  while (1 << length < n) {
    int z = mod_pow(root, max_size >> (length + 1));
    for (int i = 1 << (length - 1); i < 1 << length; i++) {
      roots[2 * i] = roots[i];
      roots[2 * i + 1] = mod_mul(roots[i], z);
    }
    length++;
  }
}
void fft_iterative(int N, vector<int> &values) {
  assert(is_power_of_two(N));
  prepare_roots(N);
  bit_reorder(N, values);
  assert(N <= max_size);
  for (int n = 1; n < N; n *= 2)
    for (int start = 0; start < N; start += 2 * n)
      for (int i = 0; i < n; i++) {
        int even = values[start + i];
        int odd = mod_mul(values[start + n + i], roots[n + i]);
        values[start + n + i] = mod_sub(even, odd);
        values[start + i] = mod_add(even, odd);
      }
}
const int FFT_CUTOFF = 150;
vector<int> mod_multiply(vector<int> left, vector<int> right,
                         bool trim = true) {
  int n = left.size();
  int m = right.size();
  for (int i = 0; i < n; i++) assert(0 <= left[i] && left[i] < MOD);
  for (int i = 0; i < m; i++) assert(0 <= right[i] && right[i] < MOD);
  if (min(n, m) < FFT_CUTOFF) {
    const uint64_t ULL_BOUND =
        numeric_limits<uint64_t>::max() - (uint64_t)MOD * MOD;
    vector<uint64_t> result(n + m - 1);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) {
        result[i + j] += (uint64_t)left[i] * right[j];
        if (result[i + j] > ULL_BOUND) result[i + j] %= MOD;
      }
    for (int i = 0; i < (int)result.size(); i++)
      if (result[i] >= (uint64_t)MOD) result[i] %= MOD;
    if (trim) {
      while (!result.empty() && result.back() == 0) result.pop_back();
    }
    return vector<int>(result.begin(), result.end());
  }
  int N = round_up_power_two(n + m - 1);
  left.resize(N);
  right.resize(N);
  bool equal = left == right;
  fft_iterative(N, left);
  if (equal)
    right = left;
  else
    fft_iterative(N, right);
  int inv_N = mod_inv(N);
  for (int i = 0; i < N; i++)
    left[i] = mod_mul(mod_mul(left[i], right[i]), inv_N);
  reverse(left.begin() + 1, left.end());
  fft_iterative(N, left);
  left.resize(n + m - 1);
  if (trim) {
    while (!left.empty() && left.back() == 0) left.pop_back();
  }
  return left;
}
vector<int> power(const vector<int> &v, int exponent) {
  assert(exponent >= 0);
  vector<int> result = {1};
  if (exponent == 0) return result;
  for (int k = 31 - __builtin_clz(exponent); k >= 0; k--) {
    result = mod_multiply(result, result);
    if (exponent & 1 << k) result = mod_multiply(result, v);
  }
  return result;
}
};  // namespace NTT
void add(int &x, int y) {
  x += y;
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
}
int fix(int x) {
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
  return x;
}
int pw(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % MOD;
    b >>= 1;
    a = 1ll * a * a % MOD;
  }
  return ret;
}
const int MAXN = 2e5 + 10;
int n, a[MAXN], sec[MAXN], sz;
vector<int> go(int b, int e) {
  if (e - b == 1) {
    vector<int> ret(sec[b] + 1, 1);
    return ret;
  }
  int mid = b + e >> 1;
  vector<int> vl = go(b, mid), vr = go(mid, e);
  return NTT::mod_multiply(vl, vr);
}
void solve() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  sort(a, a + n);
  for (int l = 0; l < n;) {
    int r = l;
    while (r < n && a[l] == a[r]) r++;
    sec[sz++] = r - l;
    l = r;
  }
  vector<int> vec = go(0, sz);
  cout << vec[n / 2] << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int te = 1;
  for (int w = 1; w <= te; w++) {
    solve();
  }
  return 0;
}
