正整数 $$$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$$$ 不是素数。