Arcaea的世界是一个二维平面，平面内的每个格点 $\{ (x,y) \mid x,y \in \mathbb{Z} \}$ 都有一片大小和厚度可忽略不计的“残片”（玻璃），每片玻璃完全一致且都与直线 $L:y=-x$ 垂直。

同时，每片玻璃还有相同的两个系数：折射系数 $a$ 和反射系数 $b$ （$a+b=1$）。

当一束强度为 $w$ 的光束沿 $x$ 轴正方向射向任意一片玻璃时，该玻璃将沿 $x$ 轴正方向射出强度为 $a\cdot w$ 的折射光束，并沿 $y$ 轴正方向射出强度为 $b\cdot w$ 的反射光束；

对称地，当一束强度为 $w$ 的光束沿 $y$ 轴正方向射向任意一片玻璃时，该玻璃将沿 $y$ 轴正方向射出强度为 $a\cdot w$ 的折射光束，并沿 $x$ 轴正方向射出强度为 $b\cdot w$ 的反射光束。

现 Hikari 在位置 $(-0.5,0)$ 向 $x$ 轴的正方向发射了强度为 1 的光束（“Fracture Ray”），并想要使其打中在位置 $(n+0.5,m)$ 的 Tairitsu；她想知道最终照射在 Tairitsu 上的光束总强度。

输入格式

第一行含一个正整数 $t$ $(1 \leq t \leq 1.25\times 10^5)$ ，表示数据组数；接下来对于每组数据：

共一行，含 4 个整数 $n,m,c,d$ ：

• $n$ 和 $m$ 的含义见上，用来确定 Tairitsu 的坐标，保证 $0 \leq n,m \leq 10^6$；
• 而对于 $c$ 和 $d$，我们约定题意中的 $a=\frac{c}{c+d}, b=\frac{d}{c+d}$ ，且保证 $0 \leq c,d < M, 1 \leq c+d < M$；
  $M=10^9+7$ ，是一个质数。

保证对于每个数据点有 $\sum n \leq 10^7, \sum m \leq 10^7$。

输出格式

对于每组数据：

可以证明，需要输出的答案“最终照射在 Tairitsu 上的光束总强度”可表示为一对互质数：非负数 $p$ 和正数 $q$ 的比值 $\frac{p}{q}$ ，且 $q$ 不是 $M=10^9+7$ 的倍数。

你需要将 $\frac{p}{q}$ 对 $M$ 取模后再输出；换而言之，找到必然存在的 $q$ 关于 $M$ 的逆元 $inv(q)$（解释见提示）后，输出

输出仅一行，含一个整数代表答案；之后换行恰好一次。

样例

输入

10
0 0 2 1
0 1 2 1
0 2 2 1
1 0 2 1
1 1 2 1
1 2 2 1
2 0 2 1
2 1 2 1
2 2 2 1
992993 994995 11009 999988997

输出

666666672
111111112
740740746
444444448
481481485
111111112
962962970
481481485
234567903
939614532

提示

样例中的前 9 个答案的真实值依次为 $\frac{2}{3},\frac{1}{9},\frac{2}{27},\frac{4}{9},\frac{4}{27},\frac{1}{9},\frac{8}{27},\frac{4}{27},\frac{10}{81}$。