Условие задачи имеет много общего с задачей 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)\). Другими словами, выведите целое число \(a\) такое, что \(0 \le a < 10^9 + 7\) и \(a \cdot y \equiv x \pmod {10^9 + 7}\).
Примечание
В первом примере у робота есть возможности очистить грязную клетку каждую секунду. Используя геометрическое распределение, мы можем вычислить, что при вероятности успеха \(25\%\) ожидаемое количество попыток очистить грязную клетку равно \(\frac 1 {0.25} = 4\). Но так как первая попытка очистки выполняется до первого движения робота, то ответ равен \(3\).
Иллюстрация к первому примеру. Робот обозначен голубой дугой. Красной звездой обозначена грязная клетка. Каждую секунду робот с некоторое вероятностью может очистить строку и столбец, что показано желтыми линиями. Во втором примере размеры доски и позиции другие, но робот все еще имеет возможность очистить строку и столбец каждую секунду с той же вероятность. Поэтому ответ такой же, как и в первом примере.
Иллюстрация ко второму примеру. Третий и четвертый примеры почти одинаковые. Единственное отличие — позиции робота и грязной клетки поменяны местами. Однако движения в этих двух примерах одинаковые, поэтому результат тоже одинаковый.