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;
const int maxm = 110;
int n, arr[110];
map<vector<int>, int> m;
vector<int> tmp;
inline int getBitsCount(int x) {
  x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
  x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
  x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
  x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
  x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
  return x;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i = (0); i < (n); ++i) cin >> arr[i];
  for (int x = (0); x < ((1 << 15)); ++x) {
    int cnt01 = getBitsCount((arr[0] ^ x) & 0x7fff);
    for (int i = (1); i < (n); ++i)
      tmp.push_back(cnt01 - getBitsCount((arr[i] ^ x) & 0x7fff));
    m.insert(make_pair(tmp, x));
    tmp.clear();
  }
  for (int x = (0); x < ((1 << 15)); ++x) {
    int cnt11 = getBitsCount(((arr[0] >> 15) ^ x) & 0x7fff);
    for (int i = (1); i < (n); ++i)
      tmp.push_back(getBitsCount(((arr[i] >> 15) ^ x) & 0x7fff) - cnt11);
    if (m.find(tmp) != m.end()) {
      cout << ((x << 15) | m[tmp]) << endl;
      return 0;
    }
    tmp.clear();
  }
  cout << -1 << endl;
  return 0;
}
