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;
const int maxt = (1 << 20);
int pow2, c2;
struct fushu {
  long double x, y;
  fushu(long double x = 0, long double y = 0) : x(x), y(y) {}
  fushu operator*(const fushu &t) const {
    return fushu(x * t.x - y * t.y, x * t.y + y * t.x);
  }
  fushu operator+(const fushu &t) const { return fushu(x + t.x, y + t.y); }
  fushu operator-(const fushu &t) const { return fushu(x - t.x, y - t.y); }
};
fushu conj(const fushu &t) { return fushu(t.x, -t.y); }
int r[maxt];
void init(int mxlen) {
  pow2 = 1;
  c2 = 0;
  while (pow2 <= mxlen) pow2 <<= 1, c2++;
  for (int i = 0; i < pow2; i++)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (c2 - 1));
}
void fft(vector<fushu> &a, int op) {
  for (int i = 0; i < pow2; i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int j = 1; j < pow2; j <<= 1) {
    fushu gen(cos(acos(-1) / j), op * sin(acos(-1) / j));
    for (int k = 0; k < pow2; k += (j << 1)) {
      fushu t(1, 0);
      for (int l = 0; l < j; l++, t = t * gen) {
        fushu nx = a[k + l], ny = t * a[k + j + l];
        a[k + l] = nx + ny;
        a[k + j + l] = nx - ny;
      }
    }
  }
}
vector<fushu> A, B, C, D;
const int maxm = 2e5 + 10;
int num[maxm], n, cnt[maxm];
vector<int> divd(int l, int r) {
  if (l == r) {
    vector<int> res;
    res.resize(cnt[l] + 1);
    for (int i = 0; i < cnt[l] + 1; i++) res[i] = 1;
    return res;
  }
  int mid = (l + r) >> 1;
  vector<int> lson = divd(l, mid);
  vector<int> rson = divd(mid + 1, r);
  init(lson.size() + rson.size() - 1);
  int nwsize = pow2;
  A.resize(nwsize);
  B.resize(nwsize);
  for (int i = 0; i < nwsize; i++) {
    A[i] =
        (i < lson.size() ? fushu(lson[i] >> 15, lson[i] & 32767) : fushu(0, 0));
    B[i] =
        (i < rson.size() ? fushu(rson[i] >> 15, rson[i] & 32767) : fushu(0, 0));
  }
  fft(A, 1);
  fft(B, 1);
  C.resize(nwsize);
  D.resize(nwsize);
  for (int i = 0; i < pow2; i++) {
    int j = i ? pow2 - i : 0;
    C[i] = ((A[i] + conj(A[j])) * (conj(B[j]) - B[i]) +
            (conj(A[j]) - A[i]) * (B[i] - conj(B[j]))) *
           fushu(0, 0.25);
    D[i] = (conj(A[j]) - A[i]) * (conj(B[j]) - B[i]) * fushu(-0.25, 0) +
           fushu(0, 0.25) * (A[i] + conj(A[j])) * (B[i] + conj(B[j]));
  }
  fft(C, -1);
  fft(D, -1);
  for (int i = 0; i < pow2; i++) {
    C[i].x /= pow2;
    C[i].y /= pow2;
    D[i].x /= pow2;
    D[i].y /= pow2;
  }
  vector<int> res;
  res.resize(pow2);
  for (int i = 0; i < pow2; i++) {
    res[i] =
        ((long long(long long(C[i].x + 0.5) % 998244353 + 998244353) % 998244353
          << 15) +
         long long(D[i].x + 0.5) +
         (long long(long long(D[i].y + 0.5) % 998244353 + 998244353) % 998244353
          << 30)) %
        998244353;
  }
  for (int i = 0; i < pow2; i++) {
  }
  return res;
}
const int maxn = 3e6 + 1;
vector<int> primes;
bool ntprime[maxn];
void getprimes() {
  for (int i = 2; i < maxn; i++) {
    if (!ntprime[i]) primes.push_back(i);
    for (int j = 0; j < primes.size() && i * primes[j] < maxn; j++) {
      ntprime[i * primes[j]] = 1;
      if (i % primes[j] == 0) break;
    }
  }
  cout << primes.size() << endl;
}
vector<int> od, lsh;
bool less2(int a, int b) { return cnt[a] < cnt[b]; }
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &num[i]);
    lsh.push_back(num[i]);
  }
  sort(lsh.begin(), lsh.end());
  lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
  for (int i = 0; i < n; i++) {
    num[i] = lower_bound(lsh.begin(), lsh.end(), num[i]) - lsh.begin();
    cnt[num[i]]++;
  }
  od.resize(lsh.size());
  for (int i = 0; i < od.size(); i++) od[i] = i;
  sort(od.begin(), od.end(), less2);
  vector<int> res = divd(0, od.size() - 1);
  int ans = 0;
  for (int i = 0; i < res.size(); i++) ans = max(ans, res[i]);
  printf("%d\n", res[n / 2]);
  return 0;
}
