光线折射

Problem Description

Arcaea的世界是一个二维平面，平面内的每个格点 { $~(x,y) ~\vert ~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上的光束总强度。

Input

第一行含一个正整数 $t ~(1 \le t \le 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$ 。

Output

对于每组数据： 可以证明，需要输出的答案“最终照射在Tairitsu上的光束总强度”可表示为一对互质数 ：非负数 $p$ 和正数 $q$ 的比值 $\frac{p}{q}$ ，且 $q$ 不是 $M=10^9+7$ 的倍数。 你需要将 $\frac{p}{q}$ 对 $M$ 取模后再输出；换而言之，找到必然存在的 $q$ 关于 $M$ 的逆元 $inv(q)$（解释见提示）后，输出 $~ (p \cdot inv(q)) \bmod M$ 。 输出仅一行，含一个整数代表答案；之后换行恰好一次。

Sample Input

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

Sample Output

666666672
111111112
740740746
444444448
481481485
111111112
962962970
481481485
234567903
939614532

Hint

样例中的前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} $ 。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（3）