P11566 【MX-X7-T7】[LSOT-3] The Witch and the Rondo of Reasoning.

Original link: . > The witch showed her empty left hand. $\\$ > Clench the left hand, toward that side, hehehe. $\\$ > Then open the right fist, and there is a candy ball in the palm. $\\$ > So, is this magic? Or a trick?

In the Golden Land, Beatrice and Battler start a red-and-blue debate on a new gameboard, whose rules are different from before. Specifically, there is an initially all-$0$ $n\times m$ board (with $n\times m$ cells). You can use Red Truth and Blue Truth on the board. Red Truth and Blue Truth each represent a rectangle, of sizes $a\times b$ and $c\times d$ respectively. To use Red Truth or Blue Truth, choose a cell on the board, then XOR all cells inside the corresponding rectangle (with that cell as the top-left corner) by $1$ (if the rectangle goes out of the board, then you cannot choose that cell). Beatrice wants to test whether some rules fit her wishes, so for each rule she asks you: by using Red Truth and Blue Truth any number of times, how many different boards can be constructed? Since the answer may be too large, you only need to output the result modulo $10^9+7$. Beatrice can restore the result by using magic.

The first line contains a positive integer $T$, indicating the number of rules Beatrice wants to test. The next $T$ lines each contain six positive integers $n, m, a, b, c, d$, with the same meanings as in the statement.

For each rule Beatrice tests, output one line with a non-negative integer, representing the number of possible boards modulo $10^9+7$.

> Without love, it cannot be seen. **[Sample Explanation]** For the first rule, neither Red Truth nor Blue Truth can be used, so there is only one case: all $0$. For the second rule, each cell can independently be $0$ or $1$, so the answer is $2^{3\times 3}=512$. For the third rule, one possible configuration is: ``` 1100 1011 0100 0100 ``` It can be generated by choosing the first cell of the first row and using Red Truth, choosing the second cell of the second row and using Blue Truth, and choosing the third cell of the third row and using Red Truth. **[Constraints]** **This problem uses bundled testdata.** - Subtask 1 (3 points): $a\mid c$, $b\mid d$. - Subtask 2 (4 points): $\sum n\times m\le 20$. - Subtask 3 (16 points): $\sum n\times m\le 1000$. - Subtask 4 (17 points): $a=b$, $c=d$. - Subtask 5 (19 points): For any two numbers among $a,b,c,d$, their $\gcd$ is $1$. - Subtask 6 (20 points): $100\times(a+b+c+d)\le \min (n,m)$. - Subtask 7 (21 points): No special properties. For all testdata, $1\le T\le10^6$, $1\le n,m,a,b,c,d \le 10^9$。 Translated by ChatGPT 5