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;
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
const int INF = 0x3f3f3f3f;
const int nINF = 1 << 31;
const int M = 998244353;
int add(long long a, long long b) { return (a + b) % M; }
int sub(long long a, long long b) { return (a + M - b) % M; }
int mult(long long a, long long b) { return (a * b) % M; }
int fastPowMod(int base, int power) {
  int res = 1;
  while (power) {
    if (power & 1) res = mult(res, base);
    base = mult(base, base);
    power >>= 1;
  }
  return res;
}
int inv(long long a) { return fastPowMod(a, M - 2); }
int choose(int n, int k) {
  int prod = 1;
  for (int i = (1); i <= (k); i++) {
    prod = mult(prod, n + 1 - i);
    prod = mult(prod, inv(i));
  }
  return prod;
}
int n, p;
map<int, int> m;
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < (n); i++) {
    cin >> p;
    ++m[p];
  }
  int d = m.size(), mn = n;
  for (auto pr : m) mn = min(mn, pr.second);
  cout << choose(add(d - 1, mn), mn) << endl;
  return 0;
}
