问题 K: 取石子游戏

由于 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$ 取模。

本题包含多组测试数据。

来自 Ayane 和 Nonomi 的温馨提示：本题输入输出量较大，对于使用 C++ 语言参加竞赛的选手，强烈建议使用关闭同步流的 cin 和 cout 完成输入输出。

首先在第一行输入一个整数 $T$（$1\le T\le 20$）表示测试数据组数。

对于每一组测试数据，输入包含四行。

第一行包含一个整数 $n$（$1\le n\le 18$），表示 $N$ 的质因子个数。

第二行包含 $n$ 个质数 p1,p2,p3,⋯,pnp1,p2,p3,⋯,pn（2≤p1<p2<p3<⋯<pn≤1072≤p1<p2<p3<⋯<pn≤107），表示 $N$ 的质因子序列。

第三行包含一个整数 $m$（0≤m≤2n0≤m≤2n），表示集合 $R$ 的大小。

第四行包含 $m$ 个整数 a1,a2,a3,⋯,ama1,a2,a3,⋯,am（0≤a1<a2<a3<⋯<am<2n0≤a1<a2<a3<⋯<am<2n），表示集合 $R$ 每个元素的特殊表示。

特殊性质：$N$ 为若干不同质数之积，且集合 $R$ 中的所有元素均是 $N$ 的因数。你需要通过以下等式计算 $N$ 与集合 $R$ 中的元素 xixi（$1\le i\le m$）的值：N=∏j=1npjN=j=1∏npjxi=∏j=1npj[(ai bitand 2j−1)>0]xi=j=1∏npj[(ai bitand 2j−1)>0]其中 $\text{bitand}$ 表示二进制按位与，$[P]$ 的值根据条件 $P$ 的真假决定，若 $P$ 为真，则 $[P]=1$，否则 $[P]=0$。

在样例的第一组测试数据中，使得在游戏中 Hoshino 必胜的 $S$ 仅有一个，满足 $S=\{17290\}$。而剩余的 $51$ 个满足条件的 $S$ 均会使得在游戏中 Shiroko 必胜。

请注意代码的常数。