CF1794D Counting Factorizations

一个正整数 $m$ 的素因数分解是将其唯一地表示为 $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 < p_2 < \ldots < 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) = \{1, 5\}$，$f(1) = \{\}$。 现在给定一个包含 $2n$ 个整数 $a_1, a_2, \ldots, a_{2n}$ 的列表。请计算有多少个正整数 $m$ 满足 $f(m) = \{a_1, a_2, \ldots, a_{2n}\}$。由于答案可能很大，请输出其对 $998\,244\,353$ 取模的结果。

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

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

在第一个样例中，满足 $f(m) = \{1,2,3,3\}$ 的 $m$ 有 $2$ 个，分别为 $m=24$ 和 $m=54$。它们的素因数分解分别为 $24=2^3\cdot 3^1$ 和 $54=2^1\cdot 3^3$。 在第二个样例中，满足 $f(m) = \{2,2,3,5\}$ 的 $m$ 有 $5$ 个，分别为 $200, 225, 288, 500$ 和 $972$。 在第三个样例中，没有任何 $m$ 满足 $f(m) = \{1,4\}$。因为 $1^4$ 和 $4^1$ 都不是素因数分解（$1$ 和 $4$ 都不是素数）。 由 ChatGPT 4.1 翻译