← 返回题目列表

Codeforces · 1794/D

D. 计算因式分解

中文机器翻译题面 查看原题

正整数 $$$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 < 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}\}$$$ 模 $$$998\,244\,353$$$ 的正整数 $$$m$$$ 的个数。

示例

输入 #1

2
1 3 2 3

输出 #1

2

输入 #2

2
2 2 3 5

输出 #2

5

输入 #3

1
1 4

输出 #3

0

注意

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

在第二个示例中,$$$m$$$ 的五个值使得 $$$f(m)=\{2,2,3,5\}$$$ 为 $$$200、225、288、500$$$ 和 $$$972$$$。

在第三个样本中,没有 $$$m$$$ 的值使得 $$$f(m)=\{1,4\}$$$。 $$$1^4$$$ 和 $$$4^1$$$ 都不是素数分解,因为 $$$1$$$ 和 $$$4$$$ 不是素数。