该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：maze.in 输出文件：maze.out

有一个由 \( R \) 行 \( C \) 列格子组成的迷宫，行按照自上向下编号为 $0 \sim R-1$，列按照自左向右编号为 $0 \sim C-1$。

迷宫的移动规则如下：

- 迷宫中的每个格子要么是墙壁，要么是空白格子。迷宫最边上一圈一定是墙壁，也就是第 $0$ 行、第 $R-1$ 行、第 $0$ 列、第 $C-1$ 列一定是墙壁。

- 当处于某个格子时，每次移动可以选择向“上 $1$ 行、下 $1$ 行、左 $1$ 列、右 $1$ 列”这 $4$ 个方向中的任意一个方向前进。

- 可以进入空白格子，但不能进入墙壁格子。

- 若在某个格子时，$4$ 个方向中共有 \( P \) 个方向对应的格子是可进入的空白格子，则选择其中任意一个可进入方向移动的概率均为 \( $\frac{1}{P}$ \)。

- 只有当 $4$ 个方向对应的格子全是墙壁时，才允许在此次移动中停留在原地。

小明希望从位于 \( $S_x$ \) 行 \( $S_y$ \) 列的起点出发，经过恰好 \( T \) 次移动后，到达位于 \( $G_x$ \) 行 \( $G_y$ \) 列的终点，起点和终点都是不是墙壁格子。

当小明按照上述概率规则移动时，最终到达终点的概率是多少？

此外，在最终到达终点的过程中，允许经过起点或终点。

输入格式

第一行三个整数 $R,C,T$。

第二行两个整数 $S_x,S_y$。

第三行两个整数 $G_x,G_y$。

接下来 $R$ 行，每行一个长度为 $C$ 的字符串，第 $i$ 行第 $j$ 列表示迷宫的编号为第 $i-1$ 行第 $j-1$ 列的格子。

输出格式

输出经过 \( T \) 次移动后位于终点的概率。

输出结果与正确答案的的绝对误差或相对误差不超过 \( 10^{-6} \) 就认为是正确的。

样例

样例 1

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

0.0208333333333333

样例 2

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

0.0143125825613343

样例 3

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

0

样例 4

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

1

数据范围

对于 40% 的数据，$T \le 100$；

对于 50% 的数据，$T \le 1000$；

对于 60% 的数据，$T \le 10^5$；

对于 100% 的数据，$3 \le R,C \le 10$，$1 \le T \le 10^8$，$0 \le S_x \le R-1$，$0 \le S_y \le R-1$，$0 \le G_x \le R-1$，$0 \le G_y \le C-1$。