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 \}.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

/***
 * G. Divisor Set
 * https://codeforces.com/problemset/problem/1257/G
 * 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 p1,p2,…,pn (2≤pi≤3⋅10^6) — the prime factorization of x.
 *
 * Output
 * Print the maximum possible size of a good subset modulo 998244353.
 * -----------------------------------------------------------------
 * Sample input :
 * 3
 * 2999999 43 2999957
 * Sample output:
 * 3
 */
public class DivisorSet {

    private static ArrayList div(int num){
        ArrayList<Integer> divisors = new ArrayList<>();
        for(int i = 2;i <= num/2;i++){
            if(num%i == 0)
                divisors.add(i);
        }
        divisors.add(num);
        return divisors;
    }
    private static boolean divisible(ArrayList<Integer> integers,int i){
        for(int val:integers){
            if(val%i == 0 || i%val == 0){
                return true;
            }
        }
        return false;
    }
    private static int largestSubset(ArrayList<Integer> divisors){
        int max = 1;
        for(int i = 0;i < divisors.size()-1;i++){
              int temp = divisors.get(i);
              ArrayList<Integer> arrayList = new ArrayList<>();
              arrayList.add(temp);
              for(int j = i+1;j < divisors.size();j++) {
                  if (!divisible(arrayList, divisors.get(j))) {
                      arrayList.add(divisors.get(j));
                  }
              }
              if(max < arrayList.size()){
                  max = arrayList.size();
              }
        }
        return max;
    }
    private static int numX(ArrayList<Integer> primesFact){
        int X = 1;
        for(int val:primesFact) {
            X = ((X%998244353)*(val%998244353))%998244353;
        }
        return X;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());
        ArrayList<Integer> primesFact = Arrays.stream(bufferedReader.readLine().split("\\s+")).map(Integer::valueOf).collect(Collectors.toCollection(ArrayList::new));
        int X = numX(primesFact);
        ArrayList<Integer> div = div(X);
        System.out.println(largestSubset(div));
    }
}
