由于 Serika 是今天的值日生，需要协助老师完成工作，因此现在 Abydos Countermeasure Committee 的活动室里只有四个人。Ayane 和 Nonomi 制作了一个颇为有趣的取石子游戏，并邀请 Shiroko 和 Hoshino 来体验。
游戏开始前有一个非空正整数 不可重集合 $S$。桌面上将会摆放 $|S|$ 堆石堆，$S$ 中的每一个元素 $i$ 都对应着一堆石子数量为 $i$ 的石堆。在游戏中 Shiroko 和 Hoshino 需要交替做出以下操作：
游戏由 Shiroko 先手。若轮到某人操作时桌面上不存在任何石堆，那么此人落败，另一人获胜。
为了增加难度，Ayane 和 Nonomi 制订了一些额外规则。Ayane 给定了一个 有特殊性质 的大整数 $N$，Nonomi 给定了一个 有特殊性质 的正整数集合 $R$。具体性质见 输入/输出格式。她们希望 $S$ 满足其中的所有元素均大于 $1$ 且它们的乘积为 $N$，并且 $S\cap R=\varnothing$。
假设 Shiroko 和 Hoshino 总是按照最优策略玩游戏。现在，你需要计算分别有多少个满足上述条件的 $S$ 使得在游戏中 Shiroko 和 Hoshino 各自必胜，答案对 $1000000007$ 取模。
本题包含多组测试数据。
提示：本题输入输出量较大，对于使用 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$。
对于每一组测试数据，输出包含一行两个整数表示使得在游戏中 Shiroko 和 Hoshino 各自必胜的 $S$ 的数量对 $1000000007$ 取模后的值。
2 5 2 5 7 13 19 0 9 2 3 5 7 11 13 17 19 23 2 4 6\n \n · · · · \n \n \n \n · · · · · · · · \n \n · \n
51 1 14749 1381· \n · \n
在样例的第一组测试数据中，使得在游戏中 Hoshino 必胜的 $S$ 仅有一个，满足 $S=\lbrace17290\rbrace$。而剩余的 $51$ 个满足条件的 $S$ 均会使得在游戏中 Shiroko 必胜。
请注意代码的常数。