取石子游戏

Problem Description

由于 Serika 是今天的值日生，需要协助老师完成工作，因此现在 Abydos Countermeasure Committee 的活动室里只有四个人。Ayane 和 Nonomi 制作了一个颇为有趣的取石子游戏，并邀请 Shiroko 和 Hoshino 来体验。 游戏开始前有一个非空正整数 不可重集合 $S$。桌面上将会摆放 $|S|$ 堆石堆，$S$ 中的每一个元素 $i$ 都对应着一堆石子数量为 $i$ 的石堆。在游戏中 Shiroko 和 Hoshino 需要交替做出以下操作：

1. 操作者任意选择一堆石堆（设其中石子数量为 $x$）与一个正整数 $y$ 满足 $x\ge y$ 且 $x$ 与 $y$ 的最大公约数为 $1$。
2. 从选择的石堆中取出 $y$ 个石子（若石堆中的石子此时被取光，也就是 $x=y$，则这堆石堆将不复存在）。 游戏由 Shiroko 先手。若轮到某人操作时桌面上不存在任何石堆，那么此人落败，另一人获胜。 为了增加难度，Ayane 和 Nonomi 制订了一些额外规则。Ayane 给定了一个 有特殊性质 的大整数 $N$，Nonomi 给定了一个 有特殊性质 的正整数集合 $R$。具体性质见 输入/输出格式。她们希望 $S$ 满足其中的所有元素均大于 $1$ 且它们的乘积为 $N$，并且 $S\cap R=\varnothing$。 假设 Shiroko 和 Hoshino 总是按照最优策略玩游戏。现在，你需要计算分别有多少个满足上述条件的 $S$ 使得在游戏中 Shiroko 和 Hoshino 各自必胜，答案对 $1000000007$ 取模。

Input

本题包含多组测试数据。 来自 Ayane 和 Nonomi 的温馨提示：本题输入输出量较大，对于使用 C++ 语言参加竞赛的选手，强烈建议使用关闭同步流的 cin 和 cout 完成输入输出。 首先在第一行输入一个整数 $T$（$1\le T\le20$）表示测试数据组数。 对于每一组测试数据，输入包含四行。 第一行包含一个整数 $n$（$1\leq n\leq18$），表示 $N$ 的质因子个数。 第二行包含 $n$ 个质数 $p_1,p_2,p_3,\cdots,p_n$（$2\leq p_1\lt p_2\lt p_3\lt \cdots\lt p_n\leq10^7$），表示 $N$ 的质因子序列。 第三行包含一个整数 $m$（$0\leq m\le2^n$），表示集合 $R$ 的大小。 第四行包含 $m$ 个整数 $a_1,a_2,a_3,\cdots,a_m$（$0\leq a_1\lt a_2\lt a_3\lt \cdots\lt a_m\lt 2^n$），表示集合 $R$ 每个元素的特殊表示。 特殊性质：$N$ 为若干不同质数之积，且集合 $R$ 中的所有元素均是 $N$ 的因数。 你需要通过以下等式计算 $N$ 与集合 $R$ 中的元素 $x_i$（$1\le i\le m$）的值：

$$N=\prod_{j=1}^np_j$$ $$x_i=\prod_{j=1}^{n}p_j^{[(a_i\ \text{bitand}\ 2^{j-1})>0]} $$

其中 $\text{bitand}$ 表示二进制按位与，$[P]$ 的值根据条件 $P$ 的真假决定，若 $P$ 为真，则 $[P]=1$，否则 $[P]=0$。

Output

对于每一组测试数据，输出包含一行两个整数表示使得在游戏中 Shiroko 和 Hoshino 各自必胜的 $S$ 的数量对 $1000000007$ 取模后的值。

Sample Input

2
5
2 5 7 13 19
0
9
2 3 5 7 11 13 17 19 23
2
4 6

Sample Output

51 1
14749 1381

Hint

在样例的第一组测试数据中，使得在游戏中 Hoshino 必胜的 $S$ 仅有一个，满足 $S=\lbrace17290\rbrace$。而剩余的 $51$ 个满足条件的 $S$ 均会使得在游戏中 Shiroko 必胜。 请注意代码的常数。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（4）