P11566 【MX-X7-T7】[LSOT-3] 魔女与推理的轮舞曲

原题链接：。 >魔女展示了空着的左手。$\\$ 把左手握上，向着那边，嘿嘿嘿。$\\$ 然后打开右拳，手心里有个糖球。$\\$ 那么，这是魔法呢？还是戏法呢？

黄金乡中，贝阿朵和战人在新的棋盘上展开的红蓝论战，这个棋盘的规则与之前的有所不同。 具体地说，有初始全 $0$ 的一个 $n\times m$ 的棋盘（格子数为 $n\times m$），可以在棋盘上使用红色真实和蓝色真实。红色真实和蓝色真实都各代表一个矩形，分别是 $a\times b$ 和 $c\times d$，使用红色真实或蓝色真实，要选择棋盘上一个格子，然后将以这个格子为左上角的那个使用的真实所对应的矩形内的所有格子异或 $1$（如果超出棋盘则不能选择此格子）。 贝阿朵想测试一些规则是否符合她的心意，所以她会问你对于某个规则，通过使用任意次红色真实与蓝色真实可以构筑出多少种不同的棋盘。 由于答案可能过大，你仅需输出对 $10^9+7$ 取模的结果即可，贝阿朵可以通过使用魔法来复原结果。

无

无

> 没有爱，就看不见。 **【样例解释】** 对于第一种规则，无法使用红色真实或蓝色真实，故只有全是 $0$ 一种情况。 对于第二种规则，每个格子都可以独立地取 $0$ 或 $1$，故答案为 $2^{3\times 3}=512$。 对于第三种规则，一种可能的局面是： ``` 1100 1011 0100 0100 ``` 生成方式为选择第一行第一个格子使用红色真实，选择第二行第二个格子使用蓝色真实，选择第三行第三个格子使用红色真实。 **【数据范围】** **本题采用捆绑测试。** - 子任务 1（3 分）：$a\mid c$，$b\mid d$。 - 子任务 2（4 分）：$\sum n\times m\le 20$。 - 子任务 3（16 分）：$\sum n\times m\le 1000$。 - 子任务 4（17 分）：$a=b$，$c=d$。 - 子任务 5（19 分）：$a,b,c,d$ 中任意两个数的 $\gcd$ 都为 $1$。 - 子任务 6（20 分）：$100\times(a+b+c+d)\le \min (n,m)$。 - 子任务 7（21 分）：无特殊性质。 对于全部的数据，$1\le T\le10^6$，$1\le n,m,a,b,c,d \le 10^9$。