在期中考试期间去校园的路上,Chaneka 想到了两个正整数 $$$X$$$ 和 $$$Y$$$。由于这两个整数可能非常大,因此都使用质因数分解来表示,例如:
- $$$X=A_1^{B_1}\times A_2^{B_2}\times\ldots\times A_N^{B_N}$$$(每个 $$$A_i$$$ 是素数,每个 $$$B_i$$$ 是正数,$$$A_1<A_2<\ldots<A_N$$$)
- $$$Y=C_1^{D_1}\times C_2^{D_2}\times\ldots\times C_M^{D_M}$$$ (每个 $$$C_j$$$ 是素数,每个 $$$D_j$$$ 是正数,并且 $$$C_1<C_2<\ldots<C_M$$$)
查内卡在整个旅程中思考这两个整数的时间太长,所以查内卡的朋友命令她“Gece,deh!” (快点)以免考试迟到。
由于该命令,Chaneka 提出了一个问题,有多少对正整数 $$$p$$$ 和 $$$q$$$ 使得 $$$\text{LCM}(p, q) = X$$$ 和 $$$\text{GCD}(p, q) = Y$$$。由于答案可能非常大,因此输出对 $$$998\,244\,353$$$ 取模的答案。
注意:
- $$$\text{LCM}(p, q)$$$ 是可同时被 $$$p$$$ 和 $$$q$$$ 整除的最小正整数。
- $$$\text{GCD}(p, q)$$$ 是同时整除 $$$p$$$ 和 $$$q$$$ 的最大正整数。
输入
第一行包含一个整数 $$$N$$$ ($$$1 \leq N \leq 10^5$$$) — $$$X$$$ 素数分解中不同素数的数量。
第二行包含 $$$N$$$ 整数 $$$A_1, A_2, A_3, \ldots, A_N$$$ ($$$2 \leq A_1 < A_2 < \ldots < A_N \leq 2 \cdot 10^6$$$; 每个 $$$A_i$$$ 都是素数) — 素数分解中的素数$$$X$$$。
第三行包含 $$$N$$$ 整数 $$$B_1, B_2, B_3, \ldots, B_N$$$ ($$$1 \leq B_i \leq 10^5$$$) — $$$X$$$ 素因式分解中的指数。
第四行包含一个整数 $$$M$$$ ($$$1 \leq M \leq 10^5$$$) — $$$Y$$$ 素数分解中不同素数的数量。
第五行包含 $$$M$$$ 整数 $$$C_1, C_2, C_3, \ldots, C_M$$$ ($$$2 \leq C_1 < C_2 < \ldots < C_M \leq 2 \cdot 10^6$$$; 每个 $$$C_j$$$ 都是素数) — 素数分解中的素数$$$Y$$$。
第六行包含 $$$M$$$ 整数 $$$D_1, D_2, D_3, \ldots, D_M$$$ ($$$1 \leq D_j \leq 10^5$$$) — $$$Y$$$ 质因数分解中的指数。
输出
一个整数,表示正整数对 $$$p$$$ 和 $$$q$$$ 的数量,使得 $$$\text{LCM}(p, q) = X$$$ 且 $$$\text{GCD}(p, q) = Y$$$,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
4 2 3 5 7 2 1 1 2 2 3 7 1 1
输出 #1
8
输入 #2
2 1299721 1999993 100000 265 2 1299721 1999993 100000 265
输出 #2
1
输入 #3
2 2 5 1 1 2 2 3 1 1
输出 #3
0
注意
在第一个示例中,整数如下:
- $$$X=2^2\times3^1\times5^1\times7^2=2940$$$
- $$$Y=3^1\times7^1=21$$$
以下是所有可能的 $$$p$$$ 和 $$$q$$$ 对:
- $$$p=21$$$,$$$q=2940$$$
- $$$p=84$$$,$$$q=735$$$
- $$$p=105$$$,$$$q=588$$$
- $$$p=147$$$,$$$q=420$$$
- $$$p=420$$$,$$$q=147$$$
- $$$p=588$$$,$$$q=105$$$
- $$$p=735$$$,$$$q=84$$$
- $$$p=2940$$$,$$$q=21$$$
在第三个示例中,整数如下:
- $$$X=2^1\times5^1=10$$$
- $$$Y=2^1\times3^1=6$$$
没有一对 $$$p$$$ 和 $$$q$$$ 同时满足 $$$\text{LCM}(p,q)=10$$$ 和 $$$\text{GCD}(p,q)=6$$$。