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 NUM = 19;
const int N = 1 << NUM;
const int P = 998244353;
const int G = 3;
inline int mul(int x, int y) {
  long long z = 1LL * x * y;
  return z - z / P * P;
}
inline int add(int x, int y) {
  x += y;
  if (x >= P) x -= P;
  return x;
}
int powt(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = mul(ans, a);
    b >>= 1;
    a = mul(a, a);
  }
  return ans;
}
namespace NTT {
const int inv_2 = (P + 1) >> 1;
int _w[N], _r[N], fast_inv[N];
void Init() {
  int wn = powt(G, (P - 1) >> NUM);
  for (int i = 1; i < N; ++i)
    _r[i] = (_r[i >> 1] >> 1) | ((i & 1) << (NUM - 1));
  _w[N >> 1] = 1;
  for (int i = (N >> 1) + 1; i < N; ++i) _w[i] = mul(_w[i - 1], wn);
  for (int i = (N >> 1) - 1; i; --i) _w[i] = _w[i << 1];
  fast_inv[0] = fast_inv[1] = 1;
  for (int i = 2; i < N; ++i) fast_inv[i] = mul(fast_inv[P % i], P - P / i);
}
int get_len(int n) {
  int x = 1;
  for (; x < n; x <<= 1)
    ;
  return x;
}
void NTT(int a[], int len, int t) {
  if (t == -1) reverse(a + 1, a + len);
  static unsigned long long tmp[N];
  int step = NUM - __builtin_ctz(len);
  for (int i = 0; i < len; ++i) tmp[i] = a[_r[i] >> step];
  for (int h = 1; h < len; h <<= 1) {
    for (int j = 0, hh = h << 1; j < len; j += hh) {
      for (int k = 0; k < h; ++k) {
        int t = tmp[j + h + k] * _w[h + k] % P;
        tmp[j | h | k] = tmp[j | k] + P - t;
        tmp[j | k] += t;
      }
    }
  }
  if (t == -1) {
    int inv = powt(len, P - 2);
    for (int i = 0; i < len; ++i) a[i] = tmp[i] * inv % P;
  } else {
    for (int i = 0; i < len; ++i) a[i] = tmp[i] % P;
  }
}
}  // namespace NTT
int f[N], a[N], b[N];
map<int, int> sq;
vector<int> solve(int l, int r) {
  vector<int> sl, sr;
  if (l == r) {
    for (int i = 0; i <= f[l]; ++i) sl.push_back(1);
    return sl;
  }
  int mid = (l + r) >> 1;
  sl = solve(l, mid);
  sr = solve(mid + 1, r);
  int l0 = sl.size();
  int l1 = sr.size();
  for (int i = 0; i < l0; ++i) a[i] = sl[i];
  for (int i = 0; i < l1; ++i) b[i] = sr[i];
  int len = NTT::get_len(l0 + l1);
  fill(a + l0, a + len, 0);
  fill(b + l1, b + len, 0);
  NTT::NTT(a, len, 1);
  NTT::NTT(b, len, 1);
  for (int i = 0; i < len; ++i) a[i] = mul(a[i], b[i]);
  NTT::NTT(a, len, -1);
  sl.resize(l0 + l1);
  for (int i = 0; i < l0 + l1; ++i) sl[i] = a[i];
  return sl;
}
int main() {
  int n, m;
  scanf("%d", &n);
  NTT::Init();
  for (int i = 0; i < n; ++i) {
    scanf("%d", &m);
    sq[m]++;
  }
  m = 0;
  for (auto e : sq) f[m++] = e.second;
  vector<int> ans = solve(0, m - 1);
  cout << ans[n / 2] << endl;
  return 0;
}
