CF1794D.Counting Factorizations

The prime factorization of a positive integer $m$ is the unique way to write it as $\displaystyle m=p_1^{e_1}\cdot p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}$, where $p_1, p_2, \ldots, p_k$ are prime numbers, $p_1 \lt p_2 \lt \ldots \lt p_k$ and $e_1, e_2, \ldots, e_k$ are positive integers.

For each positive integer $m$, $f(m)$ is defined as the multiset of all numbers in its prime factorization, that is $f(m)={p_1,e_1,p_2,e_2,\ldots,p_k,e_k}$.

For example, $f(24)={2,3,3,1}$, $f(5)={1,5}$ and $f(1)={}$.

You are given a list consisting of $2n$ integers $a_1, a_2, \ldots, a_{2n}$. Count how many positive integers $m$ satisfy that $f(m)={a_1, a_2, \ldots, a_{2n}}$. Since this value may be large, print it modulo $998\,244\,353$.

正整数 $m$ 的质因数分解是将其唯一表示为 $\displaystyle m=p_1^{e_1}\cdot p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}$ 的方式，其中 $p_1, p_2, \ldots, p_k$ 是质数，满足 $p_1 \lt p_2 \lt \ldots \lt p_k$，且 $e_1, e_2, \ldots, e_k$ 均为正整数。

对每个正整数 $m$，定义 $f(m)$ 为其质因数分解中所有数构成的多重集，即 $f(m)=\{p_1,e_1,p_2,e_2,\ldots,p_k,e_k\}$。

例如，$f(24)=\{2,3,3,1\}$，$f(5)=\{5,1\}$，而 $f(1)=\{\}$（空多重集）。

给定一个由 $2n$ 个整数 $a_1, a_2, \ldots, a_{2n}$ 组成的列表。请计算满足 $f(m)=\{a_1, a_2, \ldots, a_{2n}\}$ 的正整数 $m$ 的个数。由于该值可能很大，请输出其对 $998\,244\,353$ 取模的结果。

The first line contains one integer $n$ ($1\le n \le 2022$).

The second line contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1\le a_i\le 10^6$) — the given list.

第一行包含一个整数 $n$（$1\le n \le 2022$）。

第二行包含 $2n$ 个整数 $a_1, a_2, \ldots, a_{2n}$（$1\le a_i\le 10^6$）—— 给定的列表。

Print one integer, the number of positive integers $m$ satisfying $f(m)={a_1, a_2, \ldots, a_{2n}}$ modulo $998\,244\,353$.

输出一个整数，表示满足 $f(m)={a_1, a_2, \ldots, a_{2n}}$ 的正整数 $m$ 的个数，结果对 $998\,244\,353$ 取模。

In the first sample, the two values of $m$ such that $f(m)={1,2,3,3}$ are $m=24$ and $m=54$. Their prime factorizations are $24=2^3\cdot 3^1$ and $54=2^1\cdot 3^3$.

In the second sample, the five values of $m$ such that $f(m)={2,2,3,5}$ are $200, 225, 288, 500$ and $972$.

In the third sample, there is no value of $m$ such that $f(m)={1,4}$. Neither $1^4$ nor $4^1$ are prime factorizations because $1$ and $4$ are not primes.

在第一个样例中，满足 $f(m)={1,2,3,3}$ 的两个 $m$ 值为 $m=24$ 和 $m=54$。它们的质因数分解分别为 $24=2^3\cdot 3^1$ 和 $54=2^1\cdot 3^3$。

在第二个样例中，满足 $f(m)={2,2,3,5}$ 的五个 $m$ 值为 $200$、$225$、$288$、$500$ 和 $972$。

在第三个样例中，不存在满足 $f(m)={1,4}$ 的 $m$ 值。因为 $1$ 和 $4$ 均不是质数，所以 $1^4$ 和 $4^1$ 都不是有效的质因数分解。