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 \}.
from __future__ import division, print_function

def main():
    n = int(input())
    ar = input_as_list()

    from collections import Counter
    c = Counter(ar)
    a = sorted(c.itervalues())

    n = len(a)
    s = n
    for e in a:
        s = (s + mulmod(e-1, n-1, MOD)) % MOD
        n -= 1
    print(s)
    

INF = float('inf')
MOD = 998244353
__interactive = False

import os, sys
from atexit import register
from io import BytesIO
import itertools
import __pypy__

if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

mulmod = __pypy__.intop.int_mulmod

if "LOCAL_" in os.environ:
    debug_print = print
else:
    if not __interactive:
        sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
        sys.stdout = BytesIO()
        register(lambda: os.write(1, sys.stdout.getvalue()))

        input = lambda: sys.stdin.readline().rstrip('\r\n')
    debug_print = lambda *x, **y: None

flush = sys.stdout.flush

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def input_as_list():
    return list(map(int, input().split()))

def input_as_list_offset(o):
    return list(map(lambda x:int(x)+o, input().split()))
    
def input_as_matrix(n, m):
    return [input_as_list() for _ in range(n)]
    
def array_of(f, *dim):
    return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

def range_with_count(start, step, count):
    return range(start, start + step * count, step)

def indices(l, start=0, end=0):
    return range(start, len(l)+end)

def ceil_power_of_2(n):
    """ [0, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, ...] """
    return 2 ** ((n - 1).bit_length())

def ceil_div(x, r):
    """ = ceil(x / r) """
    return (x + r - 1) // r
    
main()