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>
template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}
using namespace std;
const int INF = 1e8 + 7;
const long long mod = 998244353;
const int M = 3e5 + 7;
const int N = 3e6 + 7;
struct NTT {
  static const int kN = (1 << 18) + 5;
  static const int ort = 3;
  static const int MOD = 998244353;
  long long power(long long a, long long b, long long p) {
    long long ret = 1;
    while (b) {
      if (b & 1) ret = ret * a % p;
      a = a * a % p;
      b >>= 1;
    }
    return ret;
  }
  void ntt(long long A[], int n, int inv) {
    long long w = 1, d = power(ort, (MOD - 1) / n, MOD), t;
    int i, j, c, s;
    if (inv == -1) {
      for (i = 1, j = n - 1; i < j; ++i, --j) std::swap(A[i], A[j]);
      for (t = power(n, MOD - 2, MOD), i = 0; i < n; ++i) A[i] = A[i] * t % MOD;
    }
    for (s = n >> 1; s; s >>= w = 1, d = d * d % MOD) {
      for (c = 0; c < s; ++c, w = w * d % MOD) {
        for (i = c; i < n; i += s << 1) {
          A[i | s] = (A[i] + MOD - (t = A[i | s])) * w % MOD;
          A[i] = (A[i] + t) % MOD;
        }
      }
    }
    for (i = 1; i < n; ++i) {
      for (j = 0, s = i, c = n >> 1; c; c >>= 1, s >>= 1) j = j << 1 | s & 1;
      if (i < j) std::swap(A[i], A[j]);
    }
  }
  void mul_ntt(long long A[], long long B[], int n) {
    ntt(A, n, 1);
    ntt(B, n, 1);
    for (int i = 0; i < n; i++) {
      A[i] = A[i] * B[i] % MOD;
    }
    ntt(A, n, -1);
  }
  void ntt_v(vector<long long>& A, int n, int inv) {
    long long w = 1, d = power(ort, (MOD - 1) / n, MOD), t;
    int i, j, c, s;
    if (inv == -1) {
      for (i = 1, j = n - 1; i < j; ++i, --j) std::swap(A[i], A[j]);
      for (t = power(n, MOD - 2, MOD), i = 0; i < n; ++i) A[i] = A[i] * t % MOD;
    }
    for (s = n >> 1; s; s >>= w = 1, d = d * d % MOD) {
      for (c = 0; c < s; ++c, w = w * d % MOD) {
        for (i = c; i < n; i += s << 1) {
          A[i | s] = (A[i] + MOD - (t = A[i | s])) * w % MOD;
          A[i] = (A[i] + t) % MOD;
        }
      }
    }
    for (i = 1; i < n; ++i) {
      for (j = 0, s = i, c = n >> 1; c; c >>= 1, s >>= 1) j = j << 1 | s & 1;
      if (i < j) std::swap(A[i], A[j]);
    }
  }
  vector<long long> mul_ntt_v(vector<long long> poly_a,
                              vector<long long> poly_b) {
    int items = poly_a.size() + poly_b.size() - 1;
    int n = 1;
    while (n < items) n <<= 1;
    poly_a.reserve(n);
    poly_b.reserve(n);
    int poly_a_size = poly_a.size();
    int poly_b_size = poly_b.size();
    for (int i = 0; i < n - poly_a_size; ++i) poly_a.push_back(0);
    for (int i = 0; i < n - poly_b_size; ++i) poly_b.push_back(0);
    ntt_v(poly_a, n, 1);
    ntt_v(poly_b, n, 1);
    for (int i = 0; i < n; i++) {
      poly_a[i] = poly_a[i] * poly_b[i] % MOD;
    }
    ntt_v(poly_a, n, -1);
    poly_a.resize(items);
    return poly_a;
  }
  vector<long long> mul_power_v(vector<long long> poly, long long exponent) {
    assert(exponent >= 0);
    vector<long long> result = {1};
    if (exponent == 0) {
      return result;
    }
    for (int k = 31 - __builtin_clz(exponent); k >= 0; k--) {
      result = mul_ntt_v(result, result);
      if ((exponent >> k) & 1) {
        result = mul_ntt_v(result, poly);
      }
    }
    return result;
  }
  vector<long long> mul_multi_v(vector<vector<long long>> polynomials) {
    if (polynomials.empty()) return {1};
    struct compare_size {
      bool operator()(const vector<long long>& x, const vector<long long>& y) {
        return x.size() > y.size();
      }
    };
    priority_queue<vector<long long>, vector<vector<long long>>, compare_size>
        pq;
    for (auto& poly : polynomials) pq.push(poly);
    while (pq.size() > 1) {
      vector<long long> a = pq.top();
      pq.pop();
      vector<long long> b = pq.top();
      pq.pop();
      pq.push(mul_ntt_v(a, b));
    }
    return pq.top();
  }
};
NTT ntt;
int n;
long long a[N];
int main() {
  ios::sync_with_stdio(false);
  ;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int v;
    cin >> v;
    ++a[v];
  }
  vector<vector<long long>> polys;
  map<int, int> mp;
  for (int i = 2; i < N; ++i) {
    ++mp[a[i]];
  }
  for (auto pi : mp) {
    vector<long long> v;
    for (int i = 0; i <= pi.first; ++i) {
      v.push_back(1);
    }
    polys.push_back(ntt.mul_power_v(v, pi.second));
  }
  auto ret = ntt.mul_multi_v(polys);
  cout << ret[ret.size() / 2] << endl;
  return 0;
}
