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;
template <class T, class V>
ostream &operator<<(ostream &s, pair<T, V> a) {
  s << a.first << ' ' << a.second;
  return s;
}
struct NTT {
  long long int MD, M = 1, R;
  vector<int> r;
  vector<long long int> w[2];
  long long int bigmod(long long int a, long long int p, long long int m) {
    long long int res = 1, x = a;
    while (p) {
      if (p & 1) res = (res * x) % m;
      x = (x * x) % m;
      p >>= 1;
    }
    return res;
  }
  long long int primitive_root(int n) {
    int p = n - 1;
    vector<int> d;
    for (int i = 2; i * i <= p; i++) {
      if (p % i == 0) {
        d.push_back(i);
        while (p % i == 0) p /= i;
      }
    }
    if (p > 1) d.push_back(p);
    for (int i = 2; i <= n; i++) {
      bool ok = true;
      for (auto x : d) ok &= (bigmod(i, (n - 1) / x, n) != 1);
      if (ok) return i;
    }
    assert(false);
  }
  NTT(long long int n, long long int _MD) : MD(_MD) {
    int u = 0;
    while (M < n) M <<= 1, u++;
    r.resize(M);
    w[0].resize(M, 1);
    w[1].resize(M, 1);
    R = primitive_root(MD);
    w[0][1] = bigmod(R, (MD - 1) / M, MD);
    w[1][1] = bigmod(w[0][1], MD - 2, MD);
    for (int i = 1; i < M; i++) {
      int l = __builtin_ctz(i);
      r[i] = r[i ^ (1 << l)] | (1 << (u - l - 1));
      w[0][i] = w[0][i - 1] * w[0][1] % MD;
      w[1][i] = w[1][i - 1] * w[1][1] % MD;
    }
  }
  void fft(vector<long long int> &a, bool inv = false) {
    for (int i = 0; i < M; i++)
      if (i < r[i]) swap(a[i], a[r[i]]);
    for (int len = 2; len <= M; len <<= 1) {
      for (int i = 0, inc = M / len; i < M; i += len) {
        for (int j = 0, l = 0; j < (len >> 1); j++, l += inc) {
          long long int u = a[i + j],
                        v = a[i + j + (len >> 1)] * w[inv][l] % MD;
          a[i + j] = (u + v >= MD ? u + v - MD : u + v);
          a[i + j + (len >> 1)] = (u < v ? u - v + MD : u - v);
        }
      }
    }
    if (inv) {
      long long int r = bigmod(M, MD - 2, MD);
      for (auto &x : a) x = x * r % MD;
    }
  }
  void multiply(vector<long long int> &a, vector<long long int> &b,
                vector<long long int> &v1) {
    v1.resize(M);
    vector<long long int> v2(M);
    for (int i = 0; i < a.size(); i++) v1[i] = a[i];
    for (int i = 0; i < b.size(); i++) v2[i] = b[i];
    fft(v1);
    fft(v2);
    for (int i = 0; i < M; i++) v1[i] = v1[i] * v2[i] % MD;
    fft(v1, 1);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  for (int qq = 1; qq <= T; qq++) {
    int n;
    cin >> n;
    map<long long int, vector<long long int>> mp;
    for (int i = 0; i < n; i++) {
      long long int x;
      cin >> x;
      mp[x].push_back(1);
    }
    if (mp.size() == 1) {
      cout << 1 << endl;
      continue;
    }
    if (n == 2) {
      cout << 2 << endl;
      continue;
    }
    int l = n / 2;
    int p = ceil(log2(l + 1));
    vector<vector<vector<long long int>>> v(18);
    vector<NTT> nt;
    for (int i = 0; i < 18; i++) nt.push_back(NTT(1 << (i + 1), (998244353)));
    for (auto x : mp) {
      x.second.push_back(1);
      int u = x.second.size();
      if (u > l + 1) x.second.resize(l + 1), u = l + 1;
      u = ceil(log2(u));
      v[u].push_back(x.second);
    }
    for (int i = 0; i < p; i++) {
      if (v[i].empty()) continue;
      int l = 0, r = v[i].size() - 1;
      while (l < r) {
        nt[i].multiply(v[i][l], v[i][r], v[i][l]);
        v[i + 1].push_back(v[i][l]);
        l++, r--;
      }
      if (l == r) v[i + 1].push_back(v[i][l]);
    }
    for (int i = 1; i < v[p].size(); i++) {
      nt[p].multiply(v[p][0], v[p][i], v[p][0]);
      v[p][0].resize(l + 1);
    }
    cout << v[p][0][l] << endl;
  }
}
