Two Balls

Mirko and Slavko are in their fourth year of high school and compete for the title of best mathematician in the school. Besides mathematics, Mirko spends his free time on computer science and Slavko on physics. Both of them passed every mathematics exam of the school year with a perfect score, so their teacher gave them one hard problem: whoever gives the more precise answer earns the title of best mathematician in the school. The problem is as follows.

A board has $R$ rows and $S$ columns ($R \times S$ cells). The centers of every two cells that share a side are connected by a groove, and there is a magnet under some of the cells. Two balls, A and B, are placed on the board and move like this:

• The balls move only along grooves. A ball needs one second to roll along a groove from the center of one cell to the center of a neighbouring cell.
• Ball A is a glass ball. Every second, A moves from its current cell along one groove to a neighbouring cell, chosen at random. Every available direction is equally likely.
• Ball B contains a magnet that repels the magnets under the board. Every second, B moves along a groove to a neighbouring cell in a direction that has no magnet at all. Whether a direction has a magnet is decided by the cells on the straight line from B's cell to the edge of the board in that direction; the cell B stands on is not considered. If every available direction has a magnet, B moves in the direction whose first magnet is farthest away. If several directions qualify equally, each of them is equally likely.

The available directions are those among up, down, left, and right that do not leave the board. Both balls move at the same time, once per second.

The balls collide if, in the same second, they move onto the same cell or meet on a groove (that is, they swap cells). Starting on the same cell is not a collision. What is the probability that the balls collide within the first $T$ seconds?

Slavko decided to solve the problem by measurement. He placed balls A and B on the given cells of a prepared board (using plastic balls instead of glass ones), waited $T$ seconds, and repeated this 1000 times. He then divided the number of runs in which the balls collided by the total number of runs. Mirko heard about this, but he knows that trial and measurement will not give a precise enough answer. He decided to write a program that computes the answer precisely to 4 decimal places and so wins the title of best mathematician.

Write a program like Mirko's that computes this probability.

The first line contains three integers $R$, $S$, and $T$: the number of rows of the board, the number of columns, and the number of seconds the balls move ($2 \le R, S \le 10$, $1 \le T \le 1000$).

The second line contains four integers $A_r$, $A_s$, $B_r$, $B_s$. Ball A starts in row $A_r$, column $A_s$, and ball B starts in row $B_r$, column $B_s$ ($1 \le A_r, B_r \le R$, $1 \le A_s, B_s \le S$). Rows are numbered from 1 starting at the top, and columns from 1 starting at the left.

Each of the next $R$ lines contains $S$ characters. P is a cell without a magnet, and M is a cell with a magnet.

Print the probability that the balls collide within the given time on a single line, rounded to 4 decimal places. Always print exactly 4 digits after the decimal point (for example, 0.2500).

The exact probability is guaranteed to be more than $10^{-7}$ away from every rounding boundary (the midpoint between two consecutive multiples of 0.0001).