Background

Original link: https://oier.team/problems/X7H.

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?

Problem Description

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.

Input Format

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.

Output Format

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

10
100 100 715 1129 123 654
3 3 1 1 2 2
4 4 2 2 3 3
4 3 4 3 3 2
20 50 15 12 10 7
50 20 33 11 25 3
107151129 147744151 715 715 1129 1129
23456 54321 1992 725 12347 7913
10000000 10000000 2222 444 3333 555
10000000 10000000 7130713 4237018 7812367 1245634

1
512
4096
32
248906884
412057510
710040542
936321181
222744797
17474728

Hint

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