题目背景

神J和神树大人正在开发一个睡眠程序，运行之后人们就能在梦里随机看到宇宙中的一角。当然大部分时候这一角都是黑的，所以人们总是觉得自己没有做梦。

神J留了个后门，只需要操控指针，就能钦定一个人的梦。于是神J天天操控神树大人梦里写代码。

神树大人很不满意，因为树必须天天睡觉。神树大人是神，早就知道神J在背后操控，所以他也留了个后门，只需要输入特殊命令，就能强迫神J睡觉，并在梦里做任何事情。

这天，神J突然发现自己身处一个大篮球场里，周围有许多学员在练习三人篮球赛。“你傻站在那干啥呢？”神树大人吹着哨子走了过来，“快去练习，都要举行肯德基三人篮球全国总决赛了，快去投进114514个球，再运球过1919810个人。zcy快过来监督他。”一个篮球突然出现在神J手里。于是神J就在zcy的监督下练习了一个下午的篮球。

题目描述

为了防止神J用篮球造出一个指针把自己指出去，神树大人钦定神J用篮球造一个矩阵。

这个矩阵无限大，行列从0开始标号，且$a[i][j]=i\ xor\ j$

现在，对于一个左上角为$(lx,ly)$，右下角为$(rx,ry)$的子矩阵，$K(K\leq 10^9)$次随机从里面取$W\times H$的矩阵，问取出的矩阵完全一样的概率，对$10^9+7$取模。

输入格式

第一行一个数$Q$表示$Q$组询问

之后$Q$行每行7个数$lx,rx,ly,ry,W,H,K$

输出格式

输出答案对$10^9+7$取模。保证答案存在。

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

提示

对于1 2 1 2 1 1 2这组询问

可以取的矩阵有：0,3，各出现两次。

有如下情况：

第一次取到 3，第二次取到 0，一共4种方法

第一次取到 3，第二次取到 3，一共4种方法

第一次取到 0，第二次取到 0，一共4种方法

第一次取到 0，第二次取到 3，一共4种方法

一共16种方法，符合条件的有4+4=8种

所以答案为 8/16=500000004(mod 10^9+7)

##数据范围

对于所有的数据，$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$

空格为无特殊限制