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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
int mapa[3000005] = {0};
int revNUM[262150];
int n;
int pos, lim;
void GCD(int a, int b, int& G, int& x, int& y) {
  if (b == 0) {
    G = a;
    x = 1;
    y = 0;
  } else {
    GCD(b, a % b, G, y, x);
    y -= ((a / b) * x);
  }
}
int modular_inverse(int num, int num_mod) {
  int x, y, G;
  GCD(num, num_mod, G, x, y);
  if (x < 0) return x + num_mod;
  return (x % num_mod);
}
int reverseNUM(int x) {
  int z = 0;
  for (int i = 0; i < pos; i++) {
    z <<= 1;
    z |= (x & 1);
    x >>= 1;
  }
  return z;
}
int mod = 998244353;
int root = 631920086;
int invroot = 114942468;
vector<vector<int> > a;
int ro[] = {857779016, 631920086, 304605202, 106061068, 64341522,  318017948,
            615001099, 586046298, 300892551, 628092333, 581015842, 280333251,
            827987769, 373294451, 625715529, 911660635, 998244352};
int inro[] = {962405921, 114942468, 948509906, 474649464, 736054570, 857007890,
              260490556, 288894979, 433414612, 91420391,  844956623, 382946991,
              543653592, 369330050, 488723995, 86583718,  998244352};
int flag = 0;
void NTT(vector<int>& v, int size, int dir, int flag) {
  for (int i = 0; i < lim; i++) {
    int& rev = revNUM[i];
    if (i < rev) {
      swap(v[i], v[rev]);
    }
  }
  for (int i = 0; i < pos; i++) {
    int m = 2 << i;
    int w = 1;
    int wm = dir == 1 ? ro[pos - flag - i] : inro[pos - flag - i];
    for (int j = 0; j < (m >> 1); j++) {
      for (int k = j; k < lim; k += m) {
        int even = v[k];
        int odd = (int)(1LL * w * v[k + (m >> 1)] % mod);
        v[k] = even + odd < mod ? even + odd : even + odd - mod;
        v[k + (m >> 1)] = even - odd >= 0 ? even - odd : even - odd + mod;
      }
      w = (int)(1LL * w * wm % mod);
    }
  }
  return;
}
void read(int& datain) {
  datain = 0;
  char c = getchar();
  while (c >= '0' && c <= '9') {
    datain = datain * 10 + (c - '0');
    c = getchar();
  }
  return;
}
int main() {
  read(n);
  int cont = 1;
  pos = 16;
  lim = 65536;
  for (int i = 0; i < lim; i++) revNUM[i] = reverseNUM(i);
  for (int i = 0; i < n; i++) {
    int x;
    read(x);
    if (mapa[x] == 0) {
      mapa[x] = cont++;
      vector<int> d;
      d.push_back(1);
      d.push_back(1);
      a.push_back(d);
    } else {
      vector<int>& d = a[mapa[x] - 1];
      d.push_back(1);
    }
  }
  sort(a.begin(), a.end());
  int conta = a[0].size();
  a[0].resize(lim, 0);
  NTT(a[0], lim, 1, flag);
  int ninv = 998229121;
  for (int i = 1; i < a.size(); i++) {
    conta += a[i].size();
    if (conta > lim) {
      NTT(a[0], lim, -1, flag);
      for (int j = 0; j < lim; j++) {
        a[0][j] = (int)((1LL * a[0][j] * ninv) % mod);
      }
      lim = lim << 1;
      pos++;
      ninv = 998236737;
      flag = 1;
      root = ro[0];
      invroot = inro[0];
      a[0].resize(lim, 0);
      NTT(a[0], lim, 1, flag);
    }
    a[i].resize(lim, 0);
    NTT(a[i], lim, 1, flag);
    for (int j = 0; j < lim; j++) {
      a[0][j] = (int)((1LL * a[0][j] * a[i][j]) % mod);
    }
  }
  NTT(a[0], lim, -1, flag);
  a[0][n / 2] = (int)((1LL * a[0][n / 2] * ninv) % mod);
  printf("%d\n", a[0][n / 2]);
  return 0;
}
