#P14536. [2026年省队模拟联测]光线折射

[2026年省队模拟联测]光线折射

题面描述

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

同时,每片玻璃还有相同的两个系数:折射系数 aa 和反射系数 bb(a+b=1a + b = 1)。

当一束强度为 ww 的光束沿 xx 轴正方向射向任意一片玻璃时,该玻璃将沿 xx 轴正方向射出强度为 a⋅wa \cdot w 的折射光束,并沿 yy 轴正方向射出强度为 b⋅wb \cdot w 的反射光束;

对称地,当一束强度为ww的光束沿yy轴正方向射向任意一片玻璃时,该玻璃将沿yy轴正方向射出强度为a⋅wa \cdot w的折射光束,并沿xx轴正方向射出强度为b⋅wb \cdot w的反射光束。

现Hikari在位置(−0.5,0)(-0.5,0)向xx轴的正方向发射了强度为1的光束("Fracture Ray"),并想要使其打中在位置(n+0.5,m)(n + 0.5,m)的Tairitsu;她想知道最终照射在Tairitsu上的光束总强度。

Input

输入共一行,含4个整数n,m,c,dn,m,c,d:

nn和mm的含义见上,用来确定Tairitsu的坐标,保证0≤n,m≤1060 \leq n,m \leq 10^6;

而对于cc和dd,我们约定题意中的a=cc+da = \frac{c}{c+d},b=dc+db = \frac{d}{c+d},且保证0≤c,d<M0 \leq c,d < M,1≤c+d<M1 \leq c + d < M;M=109+7M = 10^9 + 7,是一个质数。

Output 对于每组数据:

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

你需要将 pq\frac{p}{q} 对 MM 取模后再输出;换而言之,找到必然存在的 qq 关于MM 的逆元 inv(q)inv(q)(解释见提示)后,输出 (p⋅inv(q)) mod M(p \cdot inv(q)) \bmod M。

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

输入样例:

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个答案的真实值依次为23\frac{2}{3},19\frac{1}{9},227\frac{2}{27},49\frac{4}{9},427\frac{4}{27},19\frac{1}{9},827\frac{8}{27},427\frac{4}{27},1081\frac{10}{81}。

对于前30%30\%的数据有: n×m≤1000n\times m\leq1000

对于所有测试点有: 0≤n,m≤1060 \leq n,m \leq 10^6 0≤c,d<M0 \leq c,d < M,1≤c+d<M1 \leq c + d < M;M=109+7M = 10^9 + 7