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 P = 998244353, g = 3;
int add(int a, int b) {
  int r = a + b;
  return r < P ? r : r - P;
}
int sub(int a, int b) {
  int r = a - b;
  return r < 0 ? r + P : r;
}
int mul(long long a, long long b) { return a * b % P; }
int inv(int a) { return a == 1 ? 1 : mul(inv(P % a), P - P / a); }
int qpm(int a, long long b) {
  int r = 1;
  do
    if (b & 1) r = mul(r, a);
  while (a = mul(a, a), b >>= 1);
  return r;
}
const int W = 18, S = 1 << W;
int w[S + 1], rev[S << 1], *r[W + 1];
void init() {
  for (int s = 0; s <= W && (r[s] = rev + (1 << s), 1); ++s)
    for (int i = 0; i != (1 << s); ++i)
      r[s][i] = (r[s][i >> 1] >> 1) | ((i & 1) << (s - 1));
  w[0] = 1;
  w[1] = qpm(g, (P - 1) / S);
  for (int i = 2; i <= S; ++i) w[i] = mul(w[i - 1], w[1]);
}
int m, s, im;
int init(int n) {
  for (s = 0, m = 1; m < n; m <<= 1, ++s)
    ;
  im = inv(m);
  return m;
}
void ntt(int* p, int t) {
  for (int i = 0; i != m; ++i)
    if (i < r[s][i]) swap(p[i], p[r[s][i]]);
  for (int i = 1, z = 0; i != m; i <<= 1, z++)
    for (int j = 0; j != m; j += (i << 1))
      for (int k = 0, u, v; k != i; k++)
        u = p[j + k],
        v = mul(w[(t ? (i << 1) - k : k) << W - z - 1], p[i + j + k]),
        p[j + k] = add(u, v), p[i + j + k] = sub(u, v);
  if (t)
    for (int i = 0; i != m; ++i) p[i] = mul(p[i], im);
}
int px[S], py[S];
vector<int> mul(const vector<int>& p1, const vector<int>& p2, int n = 0) {
  int n1 = p1.size(), n2 = p2.size(), n3 = n1 + n2 - 1;
  init(n3);
  copy_n(p1.begin(), n1, px);
  fill(px + n1, px + m, 0);
  copy_n(p2.begin(), n2, py);
  fill(py + n2, py + m, 0);
  ntt(px, 0);
  ntt(py, 0);
  for (int i = 0; i != m; ++i) px[i] = mul(px[i], py[i]);
  ntt(px, 1);
  vector<int> p3(n3);
  copy_n(px, n3, p3.begin());
  if (n && n3 > n) p3.resize(n);
  return p3;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  init();
  int n;
  cin >> n;
  map<int, int> m;
  for (int i = 1; i <= n; ++i) {
    int a;
    cin >> a;
    m[a]++;
  }
  priority_queue<vector<int>, vector<vector<int>>,
                 function<bool(const vector<int>&, const vector<int>&)>>
      pq([](const vector<int>& p1, const vector<int>& p2) {
        return p1.size() > p2.size();
      });
  for (const pair<const int, int>& c : m) pq.push(vector<int>(c.second + 1, 1));
  while (pq.size() != 1) {
    vector<int> x1 = move(pq.top());
    pq.pop();
    vector<int> x2 = move(pq.top());
    pq.pop();
    pq.push(mul(x1, x2));
  }
  cout << pq.top()[n / 2] << endl;
  return 0;
}
