CF1623D.Robot Cleaner Revisit

The statement of this problem shares a lot with problem A. The differences are that in this problem, the probability is introduced, and the constraint is different.

A robot cleaner is placed on the floor of a rectangle room, surrounded by walls. The floor consists of $n$ rows and $m$ columns. The rows of the floor are numbered from $1$ to $n$ from top to bottom, and columns of the floor are numbered from $1$ to $m$ from left to right. The cell on the intersection of the $r$-th row and the $c$-th column is denoted as $(r,c)$. The initial position of the robot is $(r_b, c_b)$.

In one second, the robot moves by $dr$ rows and $dc$ columns, that is, after one second, the robot moves from the cell $(r, c)$ to $(r + dr, c + dc)$. Initially $dr = 1$, $dc = 1$. If there is a vertical wall (the left or the right walls) in the movement direction, $dc$ is reflected before the movement, so the new value of $dc$ is $-dc$. And if there is a horizontal wall (the upper or lower walls), $dr$ is reflected before the movement, so the new value of $dr$ is $-dr$.

Each second (including the moment before the robot starts moving), the robot cleans every cell lying in the same row or the same column as its position. There is only one dirty cell at $(r_d, c_d)$. The job of the robot is to clean that dirty cell.

After a lot of testings in problem A, the robot is now broken. It cleans the floor as described above, but at each second the cleaning operation is performed with probability $\frac p {100}$ only, and not performed with probability $1 - \frac p {100}$. The cleaning or not cleaning outcomes are independent each second.

Given the floor size $n$ and $m$, the robot's initial position $(r_b, c_b)$ and the dirty cell's position $(r_d, c_d)$, find the expected time for the robot to do its job.

It can be shown that the answer can be expressed as an irreducible fraction $\frac x y$, where $x$ and $y$ are integers and $y \not \equiv 0 \pmod{10^9 + 7} $. Output the integer equal to $x \cdot y^{-1} \bmod (10^9 + 7)$. In other words, output such an integer $a$ that $0 \le a \lt 10^9 + 7$ and $a \cdot y \equiv x \pmod {10^9 + 7}$.

本题的题干与问题 A 非常相似，区别在于本题引入了概率，并且约束条件不同。

一个机器人清洁器被放置在一个矩形房间的地面上，房间四周被墙壁包围。地面由 $n$ 行和 $m$ 列组成。行号从上到下依次为 $1$ 到 $n$，列号从左到右依次为 $1$ 到 $m$。第 $r$ 行与第 $c$ 列相交的格子记作 $(r,c)$。机器人的初始位置为 $(r_b, c_b)$。

每秒钟，机器人沿行方向移动 $dr$ 行、沿列方向移动 $dc$ 列；即：一秒后，机器人从格子 $(r, c)$ 移动至 $(r + dr, c + dc)$。初始时 $dr = 1$，$dc = 1$。若在移动方向上存在竖直墙壁（即左墙或右墙），则在移动前将 $dc$ 反射，即新 $dc$ 值变为 $-dc$；若在移动方向上存在水平墙壁（即上墙或下墙），则在移动前将 $dr$ 反射，即新 $dr$ 值变为 $-dr$。

每一秒（包括机器人开始移动前的初始时刻），机器人会清理其所在行或所在列上的所有格子。地面上仅有一个脏格子，位于 $(r_d, c_d)$。机器人的任务是清理该脏格子。

经过问题 A 的大量测试后，机器人现已损坏：它仍按上述方式运动并尝试清洁，但每秒的清洁操作仅以概率 $\frac{p}{100}$ 执行，以概率 $1 - \frac{p}{100}$ 不执行；各秒之间的清洁与否相互独立。

给定地面尺寸 $n$ 和 $m$、机器人初始位置 $(r_b, c_b)$ 以及脏格子位置 $(r_d, c_d)$，求机器人完成任务的期望时间。

可以证明，答案可表示为既约分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 为整数，且 $y \not\equiv 0 \pmod{10^9 + 7}$。请输出整数 $x \cdot y^{-1} \bmod (10^9 + 7)$。换言之，输出满足 $0 \le a < 10^9 + 7$ 且 $a \cdot y \equiv x \pmod{10^9 + 7}$ 的整数 $a$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$). Description of the test cases follows.

A test case consists of only one line, containing $n$, $m$, $r_b$, $c_b$, $r_d$, $c_d$, and $p$ ($4 \le n \cdot m \le 10^5$, $n, m \ge 2$, $1 \le r_b, r_d \le n$, $1 \le c_b, c_d \le m$, $1 \le p \le 99$) — the sizes of the room, the initial position of the robot, the position of the dirt cell and the probability of cleaning in percentage.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10$）。随后是各测试用例的描述。

每个测试用例仅由一行组成，包含 $n$、$m$、$r_b$、$c_b$、$r_d$、$c_d$ 和 $p$（$4 \le n \cdot m \le 10^5$，$n, m \ge 2$，$1 \le r_b, r_d \le n$，$1 \le c_b, c_d \le m$，$1 \le p \le 99$）——分别表示房间的尺寸、机器人初始位置、脏污格子的位置以及清洁概率（百分比形式）。

For each test case, print a single integer — the expected time for the robot to clean the dirty cell, modulo $10^9 + 7$.

对于每个测试用例，输出一个整数——机器人清理脏单元格的期望时间，对 $10^9 + 7$ 取模。

In the first test case, the robot has the opportunity to clean the dirty cell every second. Using the geometric distribution, we can find out that with the success rate of $25\%$, the expected number of tries to clear the dirty cell is $\frac 1 {0.25} = 4$. But because the first moment the robot has the opportunity to clean the cell is before the robot starts moving, the answer is $3$.

Illustration for the first example. The blue arc is the robot. The red star is the target dirt cell. The purple square is the initial position of the robot. Each second the robot has an opportunity to clean a row and a column, denoted by yellow stripes.

In the second test case, the board size and the position are different, but the robot still has the opportunity to clean the dirty cell every second, and it has the same probability of cleaning. Therefore the answer is the same as in the first example.

Illustration for the second example.

The third and the fourth case are almost the same. The only difference is that the position of the dirty cell and the robot are swapped. But the movements in both cases are identical, hence the same result.

在第一个测试用例中，机器人每秒都有机会清理脏单元格。利用几何分布，我们可以得出：在成功率为 $25\%$ 的情况下，清理该脏单元格所需的期望尝试次数为 $\frac{1}{0.25} = 4$。但由于机器人首次获得清理该单元格机会的时刻发生在其开始移动之前，因此答案为 $3$。

第一个示例的示意图。蓝色弧线表示机器人，红色星号表示目标脏单元格，紫色方块表示机器人的初始位置。每秒，机器人均有清理某一行和某一列的机会，以黄色条带标出。

在第二个测试用例中，棋盘尺寸与位置不同，但机器人仍每秒都有机会清理该脏单元格，且清理概率保持不变。因此答案与第一个示例相同。

第二个示例的示意图。

第三个与第四个测试用例几乎完全相同，唯一区别在于脏单元格与机器人的位置互换。但两种情形下的运动方式完全一致，故结果相同。