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 N = 6e5 + 1, M = 3e6 + 1, D = 998244353;
long long t, x, y, c[M], X, Y, n, m, f[N], g[N], l, r[N], W, w[N], V;
vector<int> a[N];
priority_queue<pair<int, int> > q;
int Q(long long a, int b) {
  t = 1;
  while (b) {
    if (b & 1) (t *= a) %= D;
    (a *= a) %= D, b /= 2;
  }
  return t;
}
void S(long long *a, int t) {
  for (int i = 0; i < n; i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1; i < n; i *= 2) {
    W = Q(3, (D - 1) / 2 / i), w[0] = 1;
    if (t < 0) W = Q(W, D - 2);
    for (int j = 1; j < i; j++) w[j] = w[j - 1] * W % D;
    for (int j = 0; j < n; j += 2 * i)
      for (int k = 0; k < i; k++)
        x = a[j + k], y = w[k] * a[i + j + k] % D, a[j + k] = (x + y) % D,
        a[i + j + k] = (x - y + D) % D;
  }
}
int main() {
  cin >> t;
  while (t-- && cin >> x) a[x].push_back(1), c[x]++;
  for (int i = 0; i < N; i++)
    if (c[i]) a[i].push_back(1), q.push(make_pair(-c[i], i));
  while (q.size() > 1) {
    X = q.top().second, n = c[X], q.pop(), Y = q.top().second, m = c[Y],
    q.pop();
    for (int i = 0; i <= n; i++) f[i] = a[X][i];
    for (int i = 0; i <= m; i++) g[i] = a[Y][i];
    m += n, n = 1, l = -1;
    while (n <= m) n *= 2, l++;
    for (int i = 0; i < n; i++) r[i] = (r[i / 2] / 2) | ((i & 1) << l);
    S(f, 1), S(g, 1);
    for (int i = 0; i < n; i++) (f[i] *= g[i]) %= D;
    S(f, -1), V = Q(n, D - 2);
    for (int i = 0; i < n; i++) (f[i] *= V) %= D;
    c[X] = m, q.push(make_pair(-m, X)), a[X].clear();
    for (int i = 0; i <= m; i++) a[X].push_back(f[i]);
    for (int i = 0; i < n; i++) f[i] = g[i] = 0;
  }
  X = q.top().second;
  cout << a[X][a[X].size() / 2];
  return 0;
}
