Description

To prevent God J from using a basketball to create a pointer and point himself out, Lord God Tree forces God J to use basketballs to build a matrix.

This matrix is infinite. Rows and columns are indexed starting from 0, and $a[i][j]=i\ xor\ j$.

Now, for a submatrix with top-left corner $(lx,ly)$ and bottom-right corner $(rx,ry)$, we randomly select a $W\times H$ matrix from it $K$ times $(K\leq 10^9)$. Ask for the probability that all selected matrices are exactly the same, modulo $10^9+7$.

Input Format

The first line contains an integer $Q$, meaning there are $Q$ queries.

Then $Q$ lines follow, each containing 7 integers $lx,rx,ly,ry,W,H,K$.

Output Format

Output the answer modulo $10^9+7$. It is guaranteed that the answer exists.

5
54 63 5 59 5 27 2
33 42 1 29 9 23 2
54 55 56 57 2 1 3
40 64 17 40 19 9 1
54 65 35 50 3 10 3

626436786
71428572
250000002
1
154489797

3
1 2 1 2 1 1 2
3 100 39 100 1 1 2
48395 309846 34098 234095 1 1 2

500000004
779746001
262016540

Hint

For the query 1 2 1 2 1 1 2:

The matrices that can be selected are: 0 and 3, each appearing twice.

There are the following cases:

First pick 3, second pick 0, a total of 4 ways.

First pick 3, second pick 3, a total of 4 ways.

First pick 0, second pick 0, a total of 4 ways.

First pick 0, second pick 3, a total of 4 ways.

There are 16 ways in total, and the valid ones are $4+4=8$ ways.

So the answer is $8/16=500000004(mod\ 10^9+7)$.

Constraints

For all testdata, $0\leq lx\leq rx\leq 10^9,0\leq ly\leq ry\leq 10^9,W\leq rx-lx+1,H\leq ry-ly+1,1\leq K\leq 10^9,Q\leq 10^3$.

Blank means there are no special constraints.

Translated by ChatGPT 5