두 구슬

미르코와 슬라브코는 고등학교 4학년이고 학교 최고의 수학자 자리를 두고 겨루고 있다. 미르코는 수학 말고도 여가 시간에 정보과학을 하고, 슬라브코는 물리학을 한다. 두 사람 모두 이번 학년 수학 시험을 전부 만점으로 통과했기 때문에 선생님은 어려운 문제 하나를 내고, 더 정확한 답을 내놓는 사람에게 학교 최고의 수학자라는 칭호를 주기로 했다. 문제는 다음과 같다.

$R$개의 행과 $S$개의 열로 이루어진 판($R \times S$개의 칸)이 있다. 변을 공유하는 두 칸의 중심은 모두 홈으로 이어져 있고, 일부 칸 아래에는 자석이 있다. 판 위에 두 구슬 A와 B를 올려 두면 구슬은 다음과 같이 움직인다.

• 구슬은 홈을 따라서만 움직인다. 구슬이 홈을 따라 한 칸의 중심에서 이웃한 칸의 중심까지 가는 데 1초가 걸린다.
• 구슬 A는 유리 구슬이다. A는 매초 지금 있는 칸에서 홈 하나를 따라 이웃한 칸으로 무작위로 움직인다. 갈 수 있는 방향 각각을 고를 확률은 모두 같다.
• 구슬 B 안에는 자석이 있어서 판 아래의 자석과 서로 밀어낸다. B는 매초 자석이 전혀 없는 방향으로 홈을 따라 이웃한 칸으로 움직인다. 어떤 방향에 자석이 있는지는 B가 있는 칸에서 그 방향으로 판 끝까지 일직선으로 늘어선 칸을 보고 정하며, B가 서 있는 칸은 보지 않는다. 모든 방향에 자석이 있으면 B는 첫 번째 자석이 가장 멀리 있는 방향으로 움직인다. 조건을 만족하는 방향이 여러 개이면 그중 각 방향을 고를 확률은 모두 같다.

갈 수 있는 방향은 위, 아래, 왼쪽, 오른쪽 가운데 판 밖으로 나가지 않는 방향이다. 두 구슬은 매초 동시에 움직인다.

같은 초에 두 구슬이 같은 칸으로 움직이거나 한 홈 위에서 서로 마주치면(서로의 칸으로 자리를 바꾸면) 두 구슬이 충돌한다고 한다. 처음에 두 구슬이 같은 칸에 놓여 있는 것은 충돌이 아니다. 처음 $T$초 안에 두 구슬이 충돌할 확률은 얼마인가?

슬라브코는 이 문제를 측정으로 풀기로 했다. 미리 준비한 판의 정해진 칸에 구슬 A와 B를 올려 두고(측정에는 유리 구슬 대신 플라스틱 구슬을 쓴다) $T$초를 기다리는 일을 1000번 반복한 다음, 구슬이 충돌한 횟수를 전체 횟수로 나누어 확률을 구했다. 이 이야기를 들은 미르코는 시행과 측정으로는 충분히 정확한 답을 얻을 수 없다는 것을 알고, 소수점 아래 4자리까지 정확한 답을 내는 프로그램을 짜서 최고의 수학자 칭호를 차지하기로 했다.

미르코처럼 이 확률을 구하는 프로그램을 작성하시오.

첫째 줄에 세 정수 $R$, $S$, $T$가 주어진다. $R$은 판의 행 수, $S$는 열 수이고 $T$는 구슬이 움직이는 시간(초)이다. ($2 \le R, S \le 10$, $1 \le T \le 1000$)

둘째 줄에 네 정수 $A_r$, $A_s$, $B_r$, $B_s$가 주어진다. 구슬 A는 $A_r$행 $A_s$열에서, 구슬 B는 $B_r$행 $B_s$열에서 출발한다. ($1 \le A_r, B_r \le R$, $1 \le A_s, B_s \le S$) 행은 위에서부터, 열은 왼쪽에서부터 1번으로 센다.

다음 $R$개 줄에는 각각 $S$개의 문자가 주어진다. P는 자석이 없는 칸, M은 자석이 있는 칸이다.

첫째 줄에 주어진 시간 안에 두 구슬이 충돌할 확률을 소수점 아래 넷째 자리까지 반올림해서 출력한다. 소수점 아래 숫자는 항상 정확히 4개를 출력한다(예: 0.2500).

정확한 확률은 반올림 경계(이웃한 두 0.0001의 배수의 한가운데)에서 항상 $10^{-7}$보다 멀리 떨어져 있음이 보장된다.