题目描述

给定 $N$ 个质数 $P_1,P_2,\dots, P_N$，再给定 $N$ 个非负整数 $A_1,A_2,\dots, A_N$，定义 $x$ 如下

也就是说，$x$ 的质因数分解可以用 $P$ 与 $A$ 来表示。同样的方法，给定 $M$ 个质数 $Q_1,Q_2,\dots, Q_M$，再给定 $M$ 个非负整数 $B_1,B_2,\dots, B_M$，定义 $y$ 如下

记 $\gcd(i, j)$ 表示整数 $i$ 与 $j$ 的最大公因数，$\text{lcm}(i,j)$ 表示整数 $i$ 与 $j$ 的最小公倍数。

请统计，有多少正整数对 $i$ 与 $j$，可以满足 $\text{lcm}(i,j)=x$ 且 $\text{gcd}(i,j)=y$。由于答案可能很大，输出方案数模 $10^9+7$ 的余数。

输入格式

• 第一行：单个整数表示 $N$
• 第二行：$N$ 个素数表示 $P_1,P_2,\dots, P_N$
• 第三行：$N$ 个非负整数表示 $A_1,A_2,\dots,A_N$
• 第四行：单个整数表示 $M$
• 第五行：$M$ 个素数表示 $Q_1,Q_2,\dots, Q_M$
• 第六行：$M$ 个非负整数表示 $B_1,B_2,\dots,B_M$
• 保证 $P_i$ 是互不相同的素数
• 保证 $Q_j$ 是互不相同的素数

输出格式

2
2 3
2 2
1
3
1

4

样例解释 1

(3,36), (9,12), (12,9), (36,3)

数据范围

• $30\%$ 的数据，$1\leq N, M\leq 5$，$0\leq A_i,B_j\leq5$，$2\leq P_i,Q_j\leq 11$
• $60\%$ 的数据，$1\leq N, M\leq 100$，$0\leq A_i,B_j\leq 100$，$2\leq P_i,Q_j\leq 1000$
• $100\%$ 的数据，$1\leq N, M\leq 100,000$，$0\leq A_i,B_j\leq 10^9$，$2\leq P_i,Q_j\leq 10^9$

来源

改编自 CF1866B Battling with Numbers