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;
#pragma comment(linker, "/STACK:10240000000,10240000000")
char ch;
int bo;
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void rd(int &x) {
  x = bo = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9';
       x = (x << 1) + (x << 3) + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline void RD(long long &x) {
  x = bo = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9';
       x = (x << 1) + (x << 3) + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline long long RD() {
  long long x;
  RD(x);
  return x;
}
inline int rd() {
  int x;
  rd(x);
  return x;
}
inline void RD(char *s) {
  for (ch = getchar(); blank(ch); ch = getchar())
    ;
  for (; !blank(ch); ch = getchar()) *s++ = ch;
  *s = 0;
}
inline void RD(char &c) {
  for (ch = getchar(); blank(c); ch = getchar())
    ;
}
const int maxn = 2e5 + 10;
const int mod = 998244353;
const double PI = acos(-1.0);
struct Complex {
  double r, i;
  Complex(double _r = 0, double _i = 0) {
    r = _r;
    i = _i;
  }
  Complex operator+(const Complex &b) { return Complex(r + b.r, i + b.i); }
  Complex operator-(const Complex &b) { return Complex(r - b.r, i - b.i); }
  Complex operator*(const Complex &b) {
    return Complex(r * b.r - i * b.i, r * b.i + i * b.r);
  }
};
void change(Complex y[], int len) {
  int i, j, k;
  for (i = 1, j = len / 2; i < len - 1; i++) {
    if (i < j) swap(y[i], y[j]);
    k = len / 2;
    while (j >= k) {
      j -= k;
      k /= 2;
    }
    if (j < k) j += k;
  }
}
void fft(Complex y[], int len, int on) {
  change(y, len);
  for (int h = 2; h <= len; h <<= 1) {
    Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h));
    for (int j = 0; j < len; j += h) {
      Complex w(1, 0);
      for (int k = j; k < j + h / 2; k++) {
        Complex u = y[k];
        Complex t = w * y[k + h / 2];
        y[k] = u + t;
        y[k + h / 2] = u - t;
        w = w * wn;
      }
    }
  }
  if (on == -1)
    for (int i = 0; i < len; i++) y[i].r /= len;
}
void deal(int a[], int b[], long long ans[], int len) {
  static Complex ta[maxn * 2], tb[maxn * 2];
  for (int i = 0; i < len; i++) {
    ta[i] = Complex(a[i], 0);
    tb[i] = Complex(b[i], 0);
  }
  fft(ta, len, 1);
  fft(tb, len, 1);
  for (int i = 0; i < len; i++) ta[i] = ta[i] * tb[i];
  fft(ta, len, -1);
  for (int i = 0; i < len; i++) ans[i] = (long long)(ta[i].r + 0.5) % mod;
}
void to_arr(vector<int> v, int a[], int len) {
  for (int i = 0; i < v.size(); i++) a[i] = v[i];
  for (int i = v.size(); i < len; i++) a[i] = 0;
}
void to_vec(vector<int> &v, long long a[], int len) {
  v.clear();
  while (a[len - 1] == 0) len--;
  for (int i = 0; i < len; i++) v.push_back(int(a[i]));
}
int get_len(int len) {
  int ret = 1;
  while (ret < len) ret *= 2;
  return ret;
}
int p[maxn];
int a[maxn];
vector<int> v[maxn];
priority_queue<pair<long long, long long>, vector<pair<long long, long long> >,
               greater<pair<long long, long long> > >
    q;
int a1[maxn * 2], a2[maxn * 2];
long long ans[maxn * 2];
int main() {
  int n = rd();
  for (int i = 0; i < n; i++) rd(p[i]);
  sort(p, p + n);
  int cnt = 0;
  int m = 0;
  p[n] = -1;
  for (int i = 0; i < n + 1; i++) {
    if (i > 0 && p[i] != p[i - 1]) {
      a[m++] = cnt;
      cnt = 1;
    } else
      cnt++;
  }
  int idx = 0;
  for (int i = 0; i < m; i++) {
    idx += a[i];
    v[i].push_back(1);
    for (int j = 0; j < a[i]; j++) v[i].push_back(1);
    q.push(pair<long long, long long>(a[i] + 1, i));
  }
  idx /= 2;
  int ans_arr = -1;
  while (1) {
    pair<long long, long long> v1 = q.top();
    q.pop();
    if (q.empty()) {
      ans_arr = v1.second;
      break;
    }
    pair<long long, long long> v2 = q.top();
    q.pop();
    int len = v1.first + v2.first;
    len = get_len(len);
    to_arr(v[v1.second], a1, len);
    to_arr(v[v2.second], a2, len);
    deal(a1, a2, ans, len);
    to_vec(v[v1.second], ans, len);
    q.push(pair<long long, long long>(v[v1.second].size(), v1.second));
  }
  printf("%d\n", v[ans_arr][idx]);
  return 0;
}
