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;
int64_t seed;
mt19937 rng(seed = chrono::steady_clock::now().time_since_epoch().count());
inline int64_t rnd(int64_t l = 0, int64_t r = INT_MAX) {
  return uniform_int_distribution<int64_t>(l, r)(rng);
}
template <typename T, typename G>
ostream &operator<<(ostream &out, const pair<T, G> &a) {
  return out << "(" << a.first << " , " << a.second << ")";
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
  out << "[";
  for (const auto &i : a) out << i << " , ";
  return out << "]" << endl;
}
template <typename T>
ostream &operator<<(ostream &out, const set<T> &a) {
  out << "{";
  for (const auto &i : a) out << i << " , ";
  return out << "}" << endl;
}
template <typename T, typename G>
ostream &operator<<(ostream &out, const map<T, G> &a) {
  out << "<";
  for (const auto &i : a) out << i << " , ";
  return out << ">" << endl;
}
template <typename T, size_t N>
typename enable_if<!is_same<typename remove_cv<T>::type, char>::value,
                   ostream &>::type
operator<<(ostream &out, T (&a)[N]) {
  out << '[';
  for (size_t i = 0; i < N; ++i) out << a[i] << " , ";
  out << "]" << endl;
  return out;
}
const int64_t mod = 998244353;
int64_t md(int64_t first, int64_t mdo = mod) {
  while (first < 0) first += mdo;
  return first % mdo;
}
int64_t multi(int64_t a, int64_t b, int64_t mdo = mod) {
  int64_t pro = 0;
  a = md(a, mdo);
  while (b) {
    if (b & 1) pro = md(md(pro, mdo) + md(a, mdo), mdo);
    a = md(a * 2, mdo);
    b >>= 1;
  }
  return pro;
}
int64_t pwr(int64_t a, int64_t n, int64_t mdo = mod) {
  if (n == 0)
    return md(1, mdo);
  else if (n == 1)
    return md(a, mdo);
  int64_t first = pwr(a, n / 2, mdo);
  if (max(first, md(a, mdo)) < int64_t(1e9))
    first = md(first * first, mdo);
  else
    first = md(multi(first, first, mdo), mdo);
  if (n & 1) {
    if (max(first, md(a, mdo)) < int64_t(1e9))
      first = md(first * md(a, mdo), mdo);
    else
      first = md(multi(first, md(a, mdo), mdo), mdo);
  }
  return first;
}
int64_t ge(int64_t a, int64_t b, int64_t *first, int64_t *second) {
  if (a == 0) {
    *first = 0, *second = 1;
    return b;
  }
  int64_t x1, y1;
  int64_t gcd = ge(b % a, a, &x1, &y1);
  *first = y1 - (b / a) * x1;
  *second = x1;
  return gcd;
}
int64_t modinv(int64_t a, int64_t m = mod) {
  int64_t first, second;
  int64_t g = ge(a, m, &first, &second);
  int64_t p = (first % m + m) % m;
  return p;
}
class ntt {
  int64_t mod, proot, max_len;
  int64_t round_pow2(int64_t n) {
    while (n & (n - 1)) {
      n = (n | (n - 1)) + 1;
    }
    return n;
  }
  int64_t find_primitive_root() {
    int64_t tot = mod - 1;
    vector<int64_t> fct;
    int64_t tmp = tot, i;
    for (i = 2; i * i <= tmp; i++) {
      if (tmp % i == 0) {
        fct.push_back(tot / i);
        while (tmp % i == 0) tmp /= i;
      }
    }
    if (tmp > 1) fct.push_back(tot / tmp);
    for (i = 2;; i++) {
      bool ok = 1;
      for (auto &f : fct) {
        if (pwr(i, f, mod) == 1) {
          ok = 0;
          break;
        }
      }
      if (ok) return i;
    }
    assert(false);
  }
  void transform(vector<int64_t> &a, bool invert) {
    int64_t n = a.size();
    assert(n <= max_len && n == round_pow2(n));
    for (int64_t i = 1, j = 0; i < n; i++) {
      int64_t bit = n >> 1;
      for (; j & bit; bit >>= 1) j ^= bit;
      j ^= bit;
      if (i < j) swap(a[i], a[j]);
    }
    int64_t add = 1;
    if (invert) add = mod - 2;
    int64_t root = pwr(proot, md((mod - 1) / n * add, mod - 1), mod);
    for (int64_t len = 2; len <= n; len <<= 1) {
      int64_t wlen = root;
      for (int64_t i = len; i < n; i <<= 1) wlen = md(wlen * wlen, mod);
      for (int64_t i = 0; i < n; i += len) {
        int64_t w = 1;
        for (int64_t j = 0; j < len / 2; j++) {
          int64_t u = a[i + j], v = md(a[i + j + len / 2] * w, mod);
          a[i + j] = md(u + v, mod);
          a[i + j + len / 2] = md(u - v, mod);
          w = md(w * wlen, mod);
        }
      }
    }
    if (invert) {
      int64_t nrev = modinv(n, mod);
      for (int64_t &first : a) first = md(first * nrev, mod);
    }
  }

 public:
  ntt(int64_t _mod) {
    mod = _mod;
    proot = find_primitive_root();
    max_len = 1;
    int64_t tot = mod - 1;
    while ((tot & max_len) == 0) max_len <<= 1;
  }
  vector<int64_t> multiply(vector<int64_t> &a, vector<int64_t> &b) {
    int64_t n = round_pow2(a.size() + b.size() - 1);
    bool eq = (a == b);
    if (a.size() != n) a.resize(n);
    if (b.size() != n) b.resize(n);
    transform(a, false);
    if (eq)
      b = a;
    else
      transform(b, false);
    for (int64_t i = 0; i < n; i++) a[i] = md(a[i] * b[i], mod);
    transform(a, true);
    while (n > 0 && a[n - 1] == 0) n--;
    a.resize(n);
    return a;
  }
};
template <typename T>
vector<int64_t> multiply_all(vector<vector<int64_t> > &polys, T trans) {
  if (polys.empty()) return {1};
  auto cmp = [&](vector<int64_t> a, vector<int64_t> b) {
    return a.size() > b.size();
  };
  priority_queue<vector<int64_t>, vector<vector<int64_t> >, decltype(cmp)> pq(
      cmp);
  for (auto &p : polys) pq.push(p);
  while (pq.size() > 1) {
    auto a = pq.top();
    pq.pop();
    auto b = pq.top();
    pq.pop();
    pq.push(trans.multiply(a, b));
  }
  return pq.top();
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int64_t n, i;
  cin >> n;
  vector<int64_t> a(n);
  for (i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int64_t c = 0, lst = a[0];
  vector<vector<int64_t> > poly;
  for (i = 0; i < n; i++) {
    if (a[i] != lst) {
      poly.push_back(vector<int64_t>(c + 1, 1));
      c = 0;
      lst = a[i];
    }
    c++;
  }
  if (c) poly.push_back(vector<int64_t>(c + 1, 1));
  ntt n1(mod);
  cout << multiply_all(poly, n1)[n / 2] << "\n";
  return 0;
}
