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>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define MAX ((int)(1e9 + 5))
#define MAXL ((ll)(1e18 + 5))
#define MAX_X ((int)(1e6 + 2))
#define pi (2.0*acos(0))
#define M ((ll)(998244353))
#define NN ((ll)(305))
#define N ((int)(2e5 + 5))
#define eps (0)
//#define log 29


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;

/*fast io
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/


typedef tree < pair < int, int >,  null_type,  less < pair < int, int > >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;
/// o_set s;
/// s.order_of_key(k) : Number of items strictly smaller than k .
/// *(s.find_by_order(k)) : K-th element in a set (counting from zero).

int main()
{
    vector < int > v , vec;
    int n;
    scanf("%d",&n);
    for(int i = 1; i<=n; i++){
        int a;
        scanf("%d",&a);
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    int last = 0;
    vec.push_back(1);
    //int sum = 1;
    for(int i = 1 ; i<v.size(); i++){
        if(v[i]==v[last]) vec.back()++;
        else{
            vec.push_back(1);
            last = i;
        }
        //sum++;
    }
    int ans = vec.size();
    sort(vec.begin(),vec.end());
    int tmp = 0;
    bool flag = 0;
    for(int i = 0; i<vec.size(); i++){
        int a = vec[i];
        //sum -= a;
        ll val = (ll)a*(vec.size() - i - 1);
        if(val>=M){
            flag = 1;
            val %= M;
        }
        tmp += val;
        if(tmp>=M){
            flag = 1;
            tmp -= M;
        }
    }

    if(vec.size()>1){
        if(vec.back()!=vec[vec.size()-2]){
            tmp++;
            if(tmp>=M){
                flag = 1;
                tmp -= M;
            }
        }
    }

    if(flag) printf("%d\n",tmp);
    else printf("%d\n",max(tmp,ans));

    return 0;
}
