统计质因数分解

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

正整数 $m$ 的质因数分解唯一写成

其中 $p_1<p_2<\cdots<p_k$ 均为质数，$e_i$ 均为正整数。定义 $f(m)$ 为分解中所有质数与指数构成的多重集：

例如 $f(24)=\{2,3,3,1\}$，$f(5)=\{1,5\}$，$f(1)=\varnothing$。

给定含有 $2n$ 个整数的列表 $a$，求有多少个正整数 $m$ 满足 $f(m)$ 恰好等于该列表表示的多重集。答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

第二行 $2n$ 个整数 $a_1,a_2,\ldots,a_{2n}$。

输出格式

输出满足条件的正整数 $m$ 的数量模 $998244353$。

样例输入 1

2
1 3 2 3

样例输出 1

2

样例输入 2

2
2 2 3 5

样例输出 2

5

样例输入 3

1
1 4

样例输出 3

0

数据范围

对于所有测试数据：

• $1\le n\le 2022$；
• $1\le a_i\le 10^6$；
• 输入恰有 $2n$ 个列表元素。

每个测试点独立计分；同一子任务内各测试点等分。