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 n;
long long f[3000010], h[3000010];
long long mp[3000010];
void init() {
  for (long long i = 2; i * i <= 3 * 1000000; i++) {
    if (f[i]) continue;
    for (long long j = 0; i * i + i * j <= 3 * 1000000; j++) {
      f[i * i + i * j] = 1;
      h[i * i + i * j] = i;
    }
  }
  for (long long i = 2; i <= 3 * 1000000; i++)
    if (h[i] == 0) h[i] = i;
}
void query(long long x) {
  while (x > 1) {
    mp[h[x]]++;
    x /= h[x];
  }
}
const long long MODULO = 998244353;
const long long ROOT = 3;
long long pw(long long x, long long y) {
  x = x % MODULO;
  long long r = 1;
  while (y) {
    if (y % 2 == 1) r = (r * x) % MODULO;
    x = (x * x) % MODULO;
    y /= 2;
  }
  return r;
}
template <class T>
long long size(const T &a) {
  return a.size();
}
unsigned roundUp(unsigned v) {
  --v;
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  return v + 1;
}
void fft(vector<long long> &a, bool invert) {
  long long n = a.size();
  assert((n & (n - 1)) == 0);
  long long lg = __builtin_ctz(n);
  for (long long i = 0; i < n; ++i) {
    long long j = 0;
    for (long long k = 0; k < lg; ++k)
      if ((i & 1 << k) != 0) j |= 1 << (lg - k - 1);
    if (i < j) swap(a[i], a[j]);
  }
  for (long long len = 2; len <= n; len *= 2) {
    long long wlen = pw(ROOT, (MODULO - 1) / len);
    if (invert) wlen = pw(wlen, MODULO - 2);
    for (long long i = 0; i < n; i += len) {
      long long w = 1;
      for (long long j = 0; j < len / 2; ++j) {
        long long u = a[i + j];
        long long v = a[i + j + len / 2] * w % MODULO;
        a[i + j] = (u + v) % MODULO;
        a[i + j + len / 2] = (u - v + MODULO) % MODULO;
        w = w * wlen % MODULO;
      }
    }
  }
  if (invert) {
    long long mul = pw(n, MODULO - 2);
    for (auto &x : a) x = x * mul % MODULO;
  }
}
vector<long long> multiply(const vector<long long> a,
                           const vector<long long> b) {
  long long n = roundUp(size(a) + size(b) - 1);
  vector<long long> pa(n), pb(n);
  for (long long i = 0; i < size(a); ++i) pa[i] = a[i];
  for (long long i = 0; i < size(b); ++i) pb[i] = b[i];
  fft(pa, false);
  fft(pb, false);
  for (long long i = 0; i < n; ++i) pa[i] = (pa[i] * pb[i]) % MODULO;
  fft(pa, true);
  vector<long long> res(n);
  for (long long i = 0; i < n; ++i) res[i] = pa[i];
  while (res.size() > 1 && res.back() == 0) res.pop_back();
  return res;
}
vector<long long> genVec(long long x) {
  vector<long long> res;
  for (long long i = 0; i <= x; i++) res.push_back(1);
  return res;
}
long long cnt = 0;
vector<long long> calc(vector<long long> a) {
  assert(!a.empty());
  if (a.size() == 1) {
    vector<long long> res;
    for (long long x = 0; x <= a[0]; x++) res.push_back(1);
    return res;
  }
  long long sum = 0;
  for (long long x : a) sum += x;
  vector<long long> rgt;
  long long temp = 0;
  while (a.size() > 1 && 2 * temp < sum) {
    temp += a.back();
    rgt.push_back(a.back());
    a.pop_back();
  }
  vector<long long> a1 = calc(a);
  vector<long long> a2 = calc(rgt);
  vector<long long> c = multiply(a1, a2);
  return c;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  init();
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    query(x);
  }
  vector<long long> factors;
  for (long long i = 2; i <= 3 * 1000000; i++) {
    if (mp[i]) {
      factors.push_back(mp[i]);
    }
  }
  random_shuffle(factors.begin(), factors.end());
  vector<long long> finals = calc(factors);
  cout << finals[n / 2];
}
