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;
ifstream f("date.in");
struct Punct {
  double x, y;
} a[10];
struct Dreapta {
  double a_dr, b_dr, c_dr;
};
int rotation_sign(Punct p1, Punct p2, Punct p3) {
  double ans = p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p2.y * p3.x -
               p3.y * p1.x - p1.y * p2.x;
  if (ans == 0) return 0;
  if (ans > 0) return 1;
  return -1;
}
bool convex() {
  if (rotation_sign(a[0], a[1], a[2]) == rotation_sign(a[1], a[2], a[3]) &&
      rotation_sign(a[1], a[2], a[3]) == rotation_sign(a[2], a[3], a[0]) &&
      rotation_sign(a[2], a[3], a[0]) == rotation_sign(a[3], a[0], a[1]) &&
      rotation_sign(a[3], a[0], a[1]) == rotation_sign(a[0], a[1], a[2])) {
    return true;
  }
  return false;
}
Dreapta get_median(Punct a1, Punct a2) {
  Punct p_mij;
  p_mij.x = (a1.x + a2.x) / 2;
  p_mij.y = (a1.y + a2.y) / 2;
  double a_dr1 = a1.y - a2.y;
  double b_dr1 = a2.x - a1.x;
  double c_dr1 = -(a_dr1 * a1.x + b_dr1 * a1.y);
  Dreapta d_dr;
  d_dr.a_dr = b_dr1;
  d_dr.b_dr = -a_dr1;
  d_dr.c_dr = -(d_dr.b_dr * p_mij.y + d_dr.a_dr * p_mij.x);
  return d_dr;
}
double get_distance(Punct p1, Punct p2) {
  return ((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
void find_4th_point() {
  Dreapta d1 = get_median(a[0], a[1]);
  Dreapta d2 = get_median(a[0], a[2]);
  Punct center_point;
  if (d1.a_dr == 0) {
    center_point.y = -d1.c_dr / d1.b_dr;
    center_point.x = (-d2.c_dr - d2.b_dr * center_point.y) / d2.a_dr;
  } else {
    center_point.y = (d2.a_dr * d1.c_dr - d2.c_dr * d1.a_dr) /
                     (d2.b_dr * d1.a_dr - d1.b_dr * d2.a_dr);
    center_point.x = (-d1.c_dr - d1.b_dr * center_point.y) / d1.a_dr;
  }
  double dist1 = get_distance(a[0], center_point);
  double dist2 = get_distance(a[3], center_point);
  if (dist1 > dist2) {
    cout << "in cerc";
  } else if (dist1 == dist2) {
    cout << "pe cerc";
  } else {
    cout << "in afara cercului";
  }
}
int main() {
  for (int i = 0; i < 4; ++i) {
    f >> a[i].x >> a[i].y;
  }
  if (convex()) {
    cout << "convex\n";
    find_4th_point();
  } else {
    cout << "neconvex\n";
  }
  return 0;
}
