Robot Cleaner Revisit

题意翻译

你住在一个 $n$ 行 $m$ 列的矩形房间里，令这个房间里面的第 $x$ 行第 $y$ 列为 $(x,y)$。有一天，你站在位置 $(r_b,c_b)$ 上，就在这时，你发现在位置 $(r_d,c_d)$ 上有一粒灰尘。于是你拿出了你最近发明的的扫地机器人准备清扫这粒灰尘。这个机器人会从你的位置开始出发，在一步以内可以从 $(r,c)$ 移动到 $(r+dr,c+dc)$。一开始，$dr=dc=1$。然而，你知道如果让机器人一直这么移动，它会撞上墙壁。于是，你在程序里面设定：如果机器人继续移动一步会撞上这个房间左边或者右边的墙壁，那么 $dc=-dc$；如果机器人继续移动一步会撞上这个房间上面或者下面的墙壁，那么 $dr=-dr$。在每开始移动一步之前，这个机器人会把它所在的行和列上的所有灰尘全部清除。 没错，事实上前面的部分和 [CF1623A](https://www.luogu.com.cn/problem/CF1623A) 一模一样。但是，你在那道题目中对这个机器人进行了太多次测试，以至于现在这个机器人出现了一些故障。具体地，这个机器人执行清除灰尘操作的概率变为 $\frac p{100}$。也就是说，机器人有 $\frac p{100}$ 的概率会清除它所在的行和列上的所有灰尘，而有 $1-\frac p{100}$ 的概率不会清除。这也使得清除 $(r_d,c_d)$ 上的灰尘所需要执行的步数变得不确定起来，所以你现在无法确定具体的步数，你只想知道，机器人清除 $(r_d,c_d)$ 上的灰尘的期望步数对 $10^9+7$ 取模之后的值是多少。 可以发现答案一定能够写成 $\frac PQ(Q\not\equiv 0\pmod{10^9+7})$ 的形式。请输出 $P\times Q^{-1}\bmod 10^9+7$ 的值。换句话来说，请输出使得 $a\times Q\equiv P\pmod{10^9+7}$ 成立的整数 $a(0\leqslant a<10^9+7)$ 的值。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10$。 - $n,m\geqslant 2$，$4\leqslant n\cdot m\leqslant 10^5$，$1\leqslant r_b,r_d\leqslant n$，$1\leqslant c_b,c_d\leqslant m$，$1\leqslant p\leqslant 99$。 Translated by Eason_AC 2021.12.29

题目描述

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} $ .

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

3
3
15
15
332103349
99224487

说明

In the first test case, the robot has the opportunity to clean the dirty cell every second. Using the [geometric distribution](https://en.wikipedia.org/wiki/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.

题意翻译

你住在一个 $n$ 行 $m$ 列的矩形房间里，令这个房间里面的第 $x$ 行第 $y$ 列为 $(x,y)$。有一天，你站在位置 $(r_b,c_b)$ 上，就在这时，你发现在位置 $(r_d,c_d)$ 上有一粒灰尘。于是你拿出了你最近发明的的扫地机器人准备清扫这粒灰尘。这个机器人会从你的位置开始出发，在一步以内可以从 $(r,c)$ 移动到 $(r+dr,c+dc)$。一开始，$dr=dc=1$。然而，你知道如果让机器人一直这么移动，它会撞上墙壁。于是，你在程序里面设定：如果机器人继续移动一步会撞上这个房间左边或者右边的墙壁，那么 $dc=-dc$；如果机器人继续移动一步会撞上这个房间上面或者下面的墙壁，那么 $dr=-dr$。在每开始移动一步之前，这个机器人会把它所在的行和列上的所有灰尘全部清除。 没错，事实上前面的部分和 [CF1623A](https://www.luogu.com.cn/problem/CF1623A) 一模一样。但是，你在那道题目中对这个机器人进行了太多次测试，以至于现在这个机器人出现了一些故障。具体地，这个机器人执行清除灰尘操作的概率变为 $\frac p{100}$。也就是说，机器人有 $\frac p{100}$ 的概率会清除它所在的行和列上的所有灰尘，而有 $1-\frac p{100}$ 的概率不会清除。这也使得清除 $(r_d,c_d)$ 上的灰尘所需要执行的步数变得不确定起来，所以你现在无法确定具体的步数，你只想知道，机器人清除 $(r_d,c_d)$ 上的灰尘的期望步数对 $10^9+7$ 取模之后的值是多少。 可以发现答案一定能够写成 $\frac PQ(Q\not\equiv 0\pmod{10^9+7})$ 的形式。请输出 $P\times Q^{-1}\bmod 10^9+7$ 的值。换句话来说，请输出使得 $a\times Q\equiv P\pmod{10^9+7}$ 成立的整数 $a(0\leqslant a<10^9+7)$ 的值。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10$。 - $n,m\geqslant 2$，$4\leqslant n\cdot m\leqslant 10^5$，$1\leqslant r_b,r_d\leqslant n$，$1\leqslant c_b,c_d\leqslant m$，$1\leqslant p\leqslant 99$。 Translated by Eason_AC 2021.12.29