Background

God J and the Great God Tree are developing a sleep program. Once run, people can randomly see a corner of the universe in their dreams. Most of the time, this corner is dark, so people always feel like they haven't dreamed.

God J left a backdoor, where by manipulating pointers, he can dictate someone's dream. Thus, God J keeps manipulating the Great God Tree to code in his dreams.

The Great God Tree is not pleased, as trees need to sleep every day. Being a god, he has long known that God J is manipulating behind the scenes, so he also left a backdoor. By entering a special command, he can force God J to sleep and do anything in his dreams.

One day, God J suddenly found himself in a large basketball court surrounded by students practicing three-on-three basketball. "Why are you standing there like a fool?" the Great God Tree, blowing a whistle, walked over. "Go practice, the KFC National Three-on-Three Basketball Finals are about to start. You need to score 114,514 baskets and dribble past 1,919,810 people. ZCY, come over and supervise him." A basketball suddenly appeared in God J's hand. Under ZCY's supervision, God J practiced basketball all afternoon.

Problem Description

To prevent God J from creating a pointer with a basketball that could eject him, the Great God Tree decreed that God J must create a matrix with the basketball.

This matrix is infinitely large, with rows and columns numbered starting from 0, and $a[i][j] = i \ xor \ j$.

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

Input Format

The first line contains a number $Q$ indicating the number of queries.

Each of the following $Q$ lines contains seven numbers $lx, rx, ly, ry, W, H, K$.

Output Format

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

Sample Input and Output

Input Sample #1

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

Output Sample #1

626436786
71428572
250000002
1
154489797

Input Sample #2

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

Output Sample #2

500000004
779746001
262016540

Notes

For the query 1 2 1 2 1 1 2:

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

The following scenarios are possible:

• First take 3, second take 0, total 4 ways.
• First take 3, second take 3, total 4 ways.
• First take 0, second take 0, total 4 ways.
• First take 0, second take 3, total 4 ways.

Total 16 ways, with 8 ways meeting the condition.

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

Data Range

For all data, $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$.

No special restrictions for spaces.

见题面 Input 部分

见题面 Output 部分