問題文

A君は$R$行$C$列のマスからなる迷路を手に入れました。
迷路を移動するルールは次のようなものです。

・迷路上の1つのマスは壁か空白のいずれかです。
・あるマスにいるとき1回で1行上、1行下、1列左、1列右の4種類のいずれかのマスの方向へ進めます。
・空白のマスに入ることはできますが、壁のマスには入ることができません。
・任意のマスで例えば4種類の方向のうち$P$種類のマスに入ることができるとき、その1種類の方向に移動する確率は$\frac{1}{P}$です。
・進むことができる4種類の方向にすべて壁がある場合のみ1回の移動でその場から移動しないことが許されます。

A君は壁でないスタート地点$Sy$行$Sx$列からちょうど$T$回の移動で壁でないゴール地点$Gy$行$Gx$列に到着したい。
A君が上記の確率で移動するときゴール地点に到着する確率はどれだけか？
なお、最終的にゴール地点に到着する途中でスタート地点、ゴール地点に移動しても良い。

入力

$R$ $C$ $T$
$Sy$ $Sx$
$Gy$ $Gx$
$B_0$
$B_1$
$⋮$
$B_{R-1}$

迷路は$R$行$C$列からなる。$3\le R,C\le 10$。
$T$はA君が移動する回数。$1\le$ T $\le 100000000={10}^8$。
スタート地点は$Sy$行$Sx$列(0-index)。$0<Sy<R-1$。$0<Sx<C-1$。
ゴール地点は$Gy$行$Gx$列(0-index)。$0<Gy<R-1$。$0<Gx<C-1$。
$B_i$は'.'か'#'からなる文字数が$C$の文字列。'.'は空白、'#'は壁をあらわす。
$B_i$は$i$行目(0-index)の迷路の状態を表しその$j$文字目(0-index)は$j$列のマスの状態をあらわす.
$Sy$行$Sx$列と$Gy$行$Gx$列はかならず空白である。
0行、$R-1$行、0列、$C-1$列のすべてのマスはかならず壁である。

出力

A君が$T$回の移動後にゴール地点にいる確率を1行で出力せよ。
ただし、正解と出力の許容誤差は絶対誤差または相対誤差が${10}^{-6}$ 以下とする。
最後に改行を忘れずに。

サンプル

6 6 5
2 1
4 4
######
###.##
#....#
###.##
##...#
######

0.0208333333333333

10 9 123
2 5
1 1
#########
#..#....#
#..#....#
#..#....#
#..#....#
#..#....#
#.......#
#..#....#
#..#....#
#########

0.0143125825613343

3 5 100000000
1 2
1 1
#####
#...#
#####

0.0000000000000000

3 3 100000000
1 1
1 1
###
#.#
###

1.0000000000000000

9 8 100000000
2 1
5 1
########
##.....#
#..###.#
###....#
##..####
#.##...#
#.#..#.#
#...##.#
########

0.0000000000000000