给你 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$。每个 $$$a_i$$$ 的除数在 $$$3$$$ 和 $$$5$$$ 之间。考虑 $$$a = \prod a_i$$$ — 所有输入整数的乘积。求 $$$a$$$ 的约数个数。由于这个数字可能非常大,因此打印它对质数 $$$998244353$$$ 的模。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 500$$$) — 数字的数量。
接下来的 $$$n$$$ 行包含一个整数 $$$a_i$$$ ($$$1 \leq a_i \leq 2\cdot 10^{18}$$$)。保证每个 $$$a_i$$$ 的因数数量在 $$$3$$$ 和 $$$5$$$ 之间。
互动
从技术角度来看,这个问题是交互式的。因此,不要忘记输出行尾并刷新输出。另外,不要阅读超出您需要的内容。要刷新输出,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
输出
打印单个整数 $$$d$$$ - 产品 $$$a_1 \cdot a_2 \cdot \dots \cdot a_n$$$ 模 $$$998244353$$$ 的除数数。
黑客输入
对于 hacks,需要以特殊格式提供输入。
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 500$$$) — 数字的数量。
接下来的 $$$n$$$ 行都包含 $$$a_i$$$ 的质因数分解。该行包含一个整数 $$$k_i$$$($$$2 \leq k_i \leq 4$$$)— $$$a_i$$$ 和 $$$k_i$$$ 整数的质因数 $$$p_{i,j}$$$($$$2 \leq p_{i,j} \leq 2 \cdot 10^{18}$$$),其中$$$p_{i,j}$$$ 是 $$$a_i$$$ 的第 $$$j$$$ 个素因子。
在向参赛者提供输入之前,计算 $$$a_i = \prod p_{i,j}$$$。请注意,每个 $$$p_{i,j}$$$ 必须是素数,每个计算出的 $$$a_i$$$ 必须满足 $$$a_i \leq 2\cdot10^{18}$$$ 并且除数必须在 $$$3$$$ 和 $$$5$$$ 之间。参赛者将仅获得 $$$a_i$$$,而不是其质因数分解。
例如,您需要使用此测试来获取第一个样本:
示例
输入 #1
3 9 15 143
输出 #1
32
输入 #2
1 7400840699802997
输出 #2
4
输入 #3
8 4606061759128693 4606066102679989 4606069767552943 4606063116488033 4606063930903637 4606064745319241 4606063930904021 4606065559735517
输出 #3
1920
输入#4
3 4 8 16
输出#4
10
注意
在第一种情况下,$$$a = 19305$$$。它的约数是 $$$1, 3, 5, 9, 11, 13, 15, 27, 33, 39, 45, 55, 65, 99, 117, 135, 143, 165, 195, 297, 351, 429, 495, 585, 715, 1287、1485、1755、2145、3861、6435、19305$$$ — 总计 $$$32$$$。
在第二种情况下,$$$a$$$ 有四个除数:$$$1$$$、$$$86028121$$$、$$$86028157$$$ 和 $$$7400840699802997 $$$。
在第三种情况下$$$a = 202600445671925364698739061629083877981962069703140268516570564888699 375209477214045102253766023072401557491054453690213483547$$$。
在第四种情况中,$$$a=512=2^9$$$,所以答案等于$$$10$$$。