Robot Cleaner Revisit
Contest: Codeforces Round 763 (Div. 2)
Difficulty rating: 2300
Tags: implementation, math, probabilities

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 < 10^9 + 7$$$ and $$$a \cdot y \equiv x \pmod {10^9 + 7}$$$.

Input format:
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.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
6
2 2 1 1 2 1 25
3 3 1 2 2 2 25
10 10 1 1 10 10 75
10 10 10 10 1 1 75
5 5 1 3 2 2 10
97 98 3 5 41 43 50

Example output:
3
3
15
15
332103349
99224487

Editorial:
In order to see how my solution actually works, let's solve this problem, the math way! You can skip to the "In general, ..." part if you don't really care about these concrete examples.
First of all, let $$$\overline{p}$$$ be the probability of not cleaning, that is, the probability that the robot will not be able to clean. So $$$\overline{p} = 1 - \frac p {100}$$$.
Let's revisit the first example again.
In this example, the robot has 2 states: when it was at position $$$(1, 1)$$$, and when it was at $$$(2, 2)$$$. Let $$$x$$$ be the answer for this problem when the robot started at $$$(1, 1)$$$, and $$$y$$$ be the answer for this problem when the robot started at $$$(2, 2)$$$.
Let's consider the first state. If the robot can clean, it spends $$$0$$$ seconds to clean the dirty cell. Otherwise, it will spend $$$1 + y$$$ seconds. Therefore, we have an equation: $$$x = \overline{p} (1 + y)$$$.
Similarly, we also have the an equation: $$$y = \overline{p}(1 + x)$$$, since these two states are symetrical. Subtituding $$$y = \overline{p}(1 + x)$$$ into $$$x = \overline{p}(1 + y)$$$, we have
$$$$$$\begin{array}{crcl} & x & = & \overline{p}(1 + \overline{p}(1 + x)) \end{array}$$$$$$
By substituting $$$\overline p$$$ in, we can find the value of $$$x$$$.
Let's consider the other example.
In this example, the robot has 4 states: when it is at $$$(1, 1)$$$, when it is at $$$(2, 2)$$$ but going to the right, when it is at $$$(1, 3)$$$, and when it is at $$$(2, 2)$$$ but going to the left. Let the answer for these states be $$$x_1, x_2, x_3,$$$ and $$$x_4$$$. Similar to the previous example, we can write down the equations:
$$$$$$ \begin{cases} x_1 = 1 + x_2 & \text{(because at }(1, 1)\text{ the robot cannot clean the dirty cell)} \\ x_2 = \overline p (1 + x_3) \\ x_3 = \overline p (1 + x_4) \\ x_4 = \overline p (1 + x_1) \end{cases} $$$$$$
Substituting these equations back to back, we can have the following equation: $$$$$$ x_1 = 1 + \overline p \left( 1 + \overline p \left( 1 + \overline p \left( 1 + x \right) \right) \right) $$$$$$
And again, if we substitute $$$\overline p$$$ in, the answer can be found easily.
In general, the path that the robot takes will form a cycle, containing the initial position. If we call $$$x$$$ the answer to the problem at the initial position, the equation we need to solve will have the following form:
$$$$$$ x = a_1 \left( 1 + a_2 \left( 1 + a_3 \left( 1 + \ldots a_k \left(1 + x \right ) \ldots \right) \right) \right) $$$$$$
where $$$k$$$ is the number of states in the cycle, and $$$a_i$$$ is some coefficient. $$$a_i = \overline p$$$ if, at the $$$i$$$-th state in the cycle, we have an opportunity to clean the dirty cell, and $$$1$$$ otherwise.
The equation can easily be solved by expanding the brackets from the innermost to the outermost, by going through the cycle in the reverse order. After the expansion, the equation will be a very simple linear equation with the form $$$x = u + vx$$$, and the solution will be $$$x = \frac u {1 - v}$$$.
To construct the equation, we can first find the cycle by either DFS or BFS, and go through the cycle in the reverse order for expansion. Or, we can do the reverse simulation, maintaining the coefficient $$$u$$$ and $$$v$$$ right away. And even better, we can just forget about the cycle and iterate exactly $$$4(n - 1)(m - 1)$$$ times (not $$$4nm$$$ though), since $$$4(n - 1)(m - 1)$$$ will always be the multiple of $$$k$$$ — the cycle length. The time complexity of this solution is $$$O(nm)$$$.