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;
long long numbit(long long x) { return (1LL << x) - 1LL; }
long long getbit(long long x, long long i) { return (x >> i) & 1LL; }
long long onbit(long long x, long long i) { return x | (1LL << i); }
long long offbit(long long x, long long i) { return x & (~(1LL << i)); }
int newMaskNULL(int mask, int m) { return (mask << 1) % (1 << m); }
int newMask(int mask, int m) { return ((mask << 1) % (1 << m)) | 1; }
const long long Inf64 = 1e18;
const long long Inf = 1e9;
const int Nmax = 1e5 + 10;
const long long Mod9 = 1e9 + 9;
const long long Mod7 = 1e9 + 7;
const int LOGN = 18;
const int MOD = 998244353;
int g = 3;
int mul(int a, int b) { return int(a * 1ll * b % MOD); }
int norm(int a) {
  while (a >= MOD) a -= MOD;
  while (a < 0) a += MOD;
  return a;
}
int binPow(int a, int k) {
  int ans = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1) ans = mul(ans, a);
    a = mul(a, a);
  }
  return ans;
}
int inv(int a) { return binPow(a, MOD - 2); }
vector<int> w[LOGN], rv;
bool precalced = false;
void precalc() {
  if (precalced) return;
  precalced = true;
  int wb = binPow(g, (MOD - 1) / (1 << LOGN));
  for (int st = int(0); st < int(LOGN); st++) {
    w[st].assign(1 << st, 1);
    int bw = binPow(wb, 1 << (LOGN - st - 1));
    int cw = 1;
    for (int k = int(0); k < int((1 << st)); k++) {
      w[st][k] = cw;
      cw = mul(cw, bw);
    }
  }
  rv.assign(1 << LOGN, 0);
  for (int i = int(1); i < int(int((rv).size())); i++)
    rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
}
const int MX = (1 << LOGN) + 3;
inline void fft(int a[MX], int n, bool inverse) {
  precalc();
  int ln = __builtin_ctz(n);
  assert((1 << ln) < MX);
  assert((1 << ln) == n);
  for (int i = int(0); i < int(n); i++) {
    int ni = rv[i] >> (LOGN - ln);
    if (i < ni) swap(a[i], a[ni]);
  }
  for (int st = 0; (1 << st) < n; st++) {
    int len = (1 << st);
    for (int k = 0; k < n; k += (len << 1)) {
      for (int pos = int(k); pos < int(k + len); pos++) {
        int l = a[pos];
        int r = mul(a[pos + len], w[st][pos - k]);
        a[pos] = norm(l + r);
        a[pos + len] = norm(l - r);
      }
    }
  }
  if (inverse) {
    int in = inv(n);
    for (int i = int(0); i < int(n); i++) a[i] = mul(a[i], in);
    reverse(a + 1, a + n);
  }
}
int aa[MX], bb[MX], cc[MX];
vector<int> multiply(const vector<int> &a, const vector<int> &b) {
  int ln = 1;
  while (ln < (int((a).size()) + int((b).size()))) ln <<= 1;
  for (int i = int(0); i < int(ln); i++)
    aa[i] = (i < int((a).size()) ? a[i] : 0);
  for (int i = int(0); i < int(ln); i++)
    bb[i] = (i < int((b).size()) ? b[i] : 0);
  fft(aa, ln, false);
  fft(bb, ln, false);
  for (int i = int(0); i < int(ln); i++) cc[i] = mul(aa[i], bb[i]);
  fft(cc, ln, true);
  vector<int> ans(cc, cc + ln);
  while (ans.back() == 0) ans.pop_back();
  return ans;
}
struct cmp {
  bool operator()(const vector<int> &a, const vector<int> &b) {
    return int((a).size()) < int((b).size());
  }
};
int main() {
  int n;
  cin >> n;
  map<int, int> cnt;
  for (long long i = (1); i <= (n); i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  multiset<vector<int>, cmp> polys;
  for (auto p : cnt) polys.emplace(p.second + 1, 1);
  while (int((polys).size()) > 1) {
    auto it2 = polys.begin();
    auto it1 = it2++;
    polys.insert(multiply(*it1, *it2));
    polys.erase(it1);
    polys.erase(it2);
  }
  auto poly = *polys.begin();
  cout << poly[n / 2] << endl;
}
