import sys
from heapq import *
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((i8, i8), cache=True)
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, i8), cache=True)
def ntt_precompute(N, primitive_root):
    roots = np.empty(1 << N, np.int64)
    iroots = np.empty(1 << N, np.int64)
    roots[0] = iroots[0] = 1
    for n in range(N):
        x = mpow(primitive_root, (MOD - 1) >> n + 2)
        y = mpow(x, MOD - 2)
        for i in range(1 << n):
            roots[(1 << n) | i] = roots[i] * x % MOD
            iroots[(1 << n) | i] = iroots[i] * y % MOD
    return roots, iroots


@njit((i8[:], i8[:], i8[:], numba.b1), cache=True)
def ntt(roots, iroots, A, inverse):
    N = len(A)
    if not inverse:
        m = N >> 1
        while m:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m] * roots[k] % MOD
                    A[i], A[i + m] = x + y, x - y
            A %= MOD
            m >>= 1
    else:
        m = 1
        while m < N:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m]
                    A[i], A[i + m] = x + y, (x - y) * iroots[k] % MOD
            A %= MOD
            m <<= 1
        invN = mpow(N, MOD - 2)
        for i in range(N):
            A[i] = A[i] * invN % MOD
    return A


@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def ntt_convolve(roots, iroots, A, B):
    n = 0
    L = len(A) + len(B) - 1
    while (1 << n) < L:
        n += 1
    A1 = np.zeros(1 << n, np.int64)
    A1[:len(A)] = A
    B1 = np.zeros(1 << n, np.int64)
    B1[:len(B)] = B
    A, B = A1, B1
    ntt(roots, iroots, A, False)
    ntt(roots, iroots, B, False)
    for i in range(len(A)):
        A[i] = A[i] * B[i] % MOD
    ntt(roots, iroots, A, True)
    return A[:L]

@njit((i8, ), cache=True)
def fact_table(N):
    """Compute 0!, 1!, ..., (N-1)! and their inverses modulo MOD. 

    Parameters
    ----------
    N : int
        length of the output array. 

    Returns
    -------
    fact : np.ndarray
        0!, 1!, ..., (N-1)!

    fact_inv : np.ndarray
        inverse of 0!, 1!, ..., (N-1)! modulo MOD. 
    """
    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD
    fact_inv = np.empty(N, np.int64)
    fact_inv[N - 1] = mpow(fact[N - 1], MOD - 2)
    for n in range(N - 1, 0, -1):
        fact_inv[n - 1] = fact_inv[n] * n % MOD
    return fact, fact_inv

@njit((i8[:], ), cache=True)
def main(H):
    max_ntt = 18
    fact, fact_inv = fact_table(110_000)
    roots, iroots = ntt_precompute(max_ntt, 3)

    def f(n, k):
        # n 人居て、k 個のペアを作る
        if k < 0 or 2 * k > n:
            return 0
        x = fact[n] * fact_inv[n - 2 * k] % MOD
        x = x * fact_inv[k] % MOD
        x = x * mpow(2, MOD - 1 - k) % MOD
        return x

    counts = np.bincount(H).astype(np.int64)
    counts = counts[counts > 0]
    N = len(counts)

    q = [(0, 0)] * 0  # 次数、インデックス
    polys = [np.zeros(0, np.int64) for _ in range(N)]
    for k in range(N):
        n = counts[k]
        P = np.empty(n // 2 + 1, np.int64)
        for i in range(n // 2 + 1):
            P[i] = f(n, i)
        polys[k] = P
        heappush(q, (len(P), k))

    while len(q) >= 2:
        _, i = heappop(q)
        _, j = heappop(q)
        P = polys[i]
        Q = polys[j]
        R = ntt_convolve(roots, iroots, P, Q)
        polys[i] = R
        heappush(q, (len(R), i))
    F = polys[q[0][1]]
    N = len(H)
    ans = 0
    for n in range(len(F)):
        x = f(N - 2 * n, N // 2 - n) * F[n] % MOD
        if n & 1:
            x = -x
        ans += x
    return ans % MOD

H = np.array(read().split(), np.int64)[1:]

print(main(H))


Measured memory_bytes: 136788