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;
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) {
      v = static_cast<Type>(x);
    } else {
      v = static_cast<Type>(x % mod());
    }
    (v < 0) && (v += mod());
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    ((value += other.value) >= mod()) && (value -= mod());
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    ((value -= other.value) < 0) && (value += mod());
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(int) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) {
    return v;
  }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, const U& rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(const U& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, const U& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const U& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, const U& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const U& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const U& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, const U& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const U& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, const U& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  for (U p = b; p > 0; p >>= 1, x *= x) {
    if (p & 1) {
      res *= x;
    }
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  if (!stream.eof()) {
    stream >> x;
    assert(!stream.fail());
    number.value = Modular<T>::normalize(x);
  }
  return stream;
}
constexpr int P = 998244353;
using ModInt = Modular<std::integral_constant<decay<decltype(P)>::type, P>>;
int fast_exponentiation(int a, int n, int p) {
  int ret = 1;
  for (; n; n >>= 1, a = a * 1LL * a % p) {
    if (n & 1) {
      ret = ret * 1LL * a % p;
    }
  }
  return ret;
}
namespace FFT {
const int M = 1 << 18;
int IM;
ModInt a1[M], b1[M];
ModInt p[M + 1];
template <typename T>
void NTT(T* B, T* A, int N, int D) {
  for (int i = 0, j = 0; i < N - 1; i++) {
    A[i] = B[j];
    for (int k = N / 2; (j ^= k) < k; k >>= 1)
      ;
  }
  for (int n = 1, m = M / 2 * D; n < N; m /= 2, n <<= 1) {
    for (int i = 0; i < N; i += n << 1) {
      T *w = (D == 1 ? p : p + M), *a = A + i, *b = A + i + n;
      for (int j = 0; j < n; j++, a++, b++, w += m) {
        T x = *w * *b;
        *b = *a - x;
        *a += x;
      }
    }
  }
}
void init() {
  int fac[10] = {0}, n = 0;
  for (int Q = P - 1, q = 2; Q > 1; q++)
    if (Q % q == 0) {
      fac[n++] = q;
      while (Q % q == 0) {
        Q /= q;
      }
    }
  int G = 2;
  while (1) {
    int flg = 1;
    for (int i = 0; i < n; i++) {
      if (fast_exponentiation(G, P / fac[i], P) == 1) {
        flg = 0;
      }
    }
    if (flg) break;
    G++;
  }
  G = fast_exponentiation(G, P / M, P);
  for (int i = 0; i <= M; i++) {
    p[i] = i == 0 ? 1 : p[i - 1] * G;
  }
  IM = fast_exponentiation(M, P - 2, P);
}
template <typename T>
void multiply(T* a, T* b, T* c, int N) {
  if (N <= 64) {
    static T temp[64];
    memset(temp, 0, sizeof(T) * N);
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N - i; j++) {
        temp[i + j] += a[i] * b[j];
      }
      for (int j = N - i; j < N; j++) {
        temp[i + j - N] += a[i] * b[j];
      }
    }
    memcpy(c, temp, sizeof(T) * N);
    return;
  }
  NTT(a, a1, N, 1);
  NTT(b, b1, N, 1);
  T R = 1LL * IM * (M / N) % P;
  for (int i = 0; i < N; i++) {
    a1[i] *= b1[i] * R;
  }
  NTT(a1, c, N, -1);
}
};  // namespace FFT
const int N = 1 << 18;
template <typename T>
vector<T> multiply(const vector<T>& a, const vector<T>& b) {
  if (a.empty() || b.empty()) {
    return vector<T>();
  }
  int m = a.size() + b.size() - 2;
  int n = 1 << 32 - __builtin_clz(a.size() + b.size() - 2);
  static T __a[N], __b[N], __c[N];
  for (int i = 0; i < n; i++) {
    __a[i] = i < a.size() ? a[i] : 0;
    __b[i] = i < b.size() ? b[i] : 0;
  }
  FFT::multiply(__a, __b, __c, n);
  return vector<T>(__c, __c + m + 1);
}
using Polynomial = vector<ModInt>;
Polynomial& operator*=(Polynomial& lhs, const Polynomial& rhs) {
  return lhs = multiply(lhs, rhs);
}
Polynomial operator*(const Polynomial& lhs, const Polynomial& rhs) {
  Polynomial ret(lhs);
  return ret *= rhs;
}
Polynomial product(const vector<Polynomial>& a) {
  function<bool(Polynomial, Polynomial)> compare =
      [&](Polynomial lhs, Polynomial rhs) { return lhs.size() < rhs.size(); };
  priority_queue<Polynomial, vector<Polynomial>, decltype(compare)> Q(
      a.begin(), a.end(), compare);
  while (Q.size() > 1) {
    auto x = Q.top();
    Q.pop();
    auto y = Q.top();
    Q.pop();
    Q.push(x * y);
  }
  return Q.top();
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  FFT::init();
  int n;
  cin >> n;
  map<int, int> cnt;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  vector<Polynomial> a;
  for (auto t : cnt) {
    a.push_back(Polynomial(t.second + 1, 1));
  }
  cout << product(a)[n / 2] << '\n';
  return 0;
}
