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>
inline void read(char &x) {
  do x = getchar();
  while (x <= ' ');
}
inline void read(char *s) {
  char ch;
  do ch = getchar();
  while (ch <= ' ');
  while (ch > ' ') {
    (*s) = ch;
    s++;
    ch = getchar();
  }
  (*s) = 0;
}
inline void read(std::string &s) {
  char ch;
  do ch = getchar();
  while (ch <= ' ');
  while (ch > ' ') {
    s.push_back(ch);
    ch = getchar();
  }
}
template <class A>
inline void readint(A &x) {
  bool neg = false;
  char ch;
  do ch = getchar();
  while (ch <= ' ');
  if (ch == '-') {
    neg = true;
    ch = getchar();
  }
  x = 0;
  while (ch > ' ') {
    x = x * 10 + (ch & 15);
    ch = getchar();
  }
  if (neg) x = -x;
}
inline void read(int &x) { readint(x); }
inline void read(long long &x) { readint(x); }
template <class A, class B>
inline void read(A &a, B &b) {
  read(a);
  read(b);
}
template <class A, class B, class C>
inline void read(A &a, B &b, C &c) {
  read(a);
  read(b);
  read(c);
}
template <class A, class B, class C, class D>
inline void read(A &a, B &b, C &c, D &d) {
  read(a);
  read(b);
  read(c);
  read(d);
}
inline void writeln() { putchar('\n'); }
template <class A>
inline void write(A x) {
  static char buf[20];
  int top = 0;
  if (!x) {
    putchar('0');
    return;
  }
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  while (x) {
    buf[++top] = (x % 10) | 48;
    x /= 10;
  }
  while (top) putchar(buf[top--]);
}
template <class A>
inline void write_(A x) {
  write(x);
  putchar(' ');
}
template <class A>
inline void writeln(A x) {
  write(x);
  putchar('\n');
}
template <class A, class B>
inline void write(A a, B b) {
  write_(a);
  write(b);
}
template <class A, class B>
inline void writeln(A a, B b) {
  write_(a);
  writeln(b);
}
template <class A, class B, class C>
inline void writeln(A a, B b, C c) {
  write_(a);
  write_(b);
  writeln(c);
}
template <class A, class B, class C, class D>
inline void writeln(A a, B b, C c, D d) {
  write_(a);
  write_(b);
  write_(c);
  writeln(d);
}
const int MOD = 998244353;
const int G = 3;
const int LOGN = 18;
const int LEN = 1 << LOGN;
const int N = 2e5 + 10;
int n, n0;
int pool[N];
int size[N], *f[N];
int INVGN[LOGN + 2], GN[LOGN + 2];
inline void qmod(int &x) { x = (x >= MOD) ? (x - MOD) : x; }
inline int qpow(long long b, int p, int mod = MOD) {
  int res = 1;
  while (p) {
    if (p & 1) res = res * b % mod;
    b = b * b % mod;
    p >>= 1;
  }
  return res;
}
void initgn() {
  int i, k;
  for (i = k = 1; i <= LOGN; i++, k <<= 1) {
    GN[i] = qpow(G, (MOD - 1) / (k << 1));
    INVGN[i] = qpow(GN[i], MOD - 2);
  }
}
void dft(int a[], int len, bool inv = false) {
  static int rev[LEN | 5];
  int i, j, k, logk;
  int gn, t;
  long long g;
  k = 1;
  while (len >> k >> 1) k++;
  for (i = int(1); i <= int(len - 1); i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
  for (i = 1; i < len; i++)
    if (i < rev[i]) std::swap(a[i], a[rev[i]]);
  for (k = logk = 1; k < len; k <<= 1, logk++) {
    gn = inv ? INVGN[logk] : GN[logk];
    for (i = 0; i < len; i += k << 1) {
      g = 1;
      for (j = 0; j < k; j++) {
        t = g * a[i + j + k] % MOD;
        qmod(a[i + j + k] = a[i + j] + MOD - t);
        qmod(a[i + j] = a[i + j] + t);
        g = g * gn % MOD;
      }
    }
  }
  if (inv) {
    g = qpow(len, MOD - 2);
    for (i = 0; i < len; i++) a[i] = a[i] * g % MOD;
  }
}
inline void idft(int *a, int len) { dft(a, len, true); }
void polymul(int *a, int *b, int n, int m) {
  static int aa[LEN | 5], bb[LEN | 5];
  int i, len;
  len = 1;
  while (len <= n + m) len <<= 1;
  for (i = 0; i <= n; i++) aa[i] = a[i];
  for (i = 0; i <= m; i++) bb[i] = b[i];
  dft(aa, len);
  dft(bb, len);
  for (i = 0; i < len; i++) aa[i] = 1LL * aa[i] * bb[i] % MOD;
  idft(aa, len);
  for (i = 0; i <= n + m; i++) a[i] = aa[i];
  for (i = 0; i < len; i++) aa[i] = bb[i] = 0;
}
void input() {
  static int p[N];
  int l, r, i;
  int *ptr = pool;
  read(n0);
  for (i = int(1); i <= int(n0); i++) read(p[i]);
  std::sort(p + 1, p + n0 + 1);
  for (l = 1; l <= n0; l = r) {
    r = l;
    while (p[l] == p[r]) r++;
    n++;
    size[n] = r - l;
    f[n] = ptr;
    for (i = int(1); i <= int(r - l + 1); i++) {
      (*ptr) = 1;
      ptr++;
    }
  }
}
int main() {
  int i, j, k;
  initgn();
  input();
  for (k = 1; k < n; k <<= 1) {
    for (i = 1; i + k <= n; i += k << 1) {
      polymul(f[i], f[i + k], size[i], size[i + k]);
      size[i] += size[i + k];
    }
  }
  printf("%d\n", f[1][(n0 + 1) >> 1]);
  return 0;
}
