题目背景

网格城由纵横交错的街道组成，整座城市可以看成一个矩形网格。游客 Alice 从城市的西北角出发，准备一路向东南方向前往终点。

为了避免迷路，她只会向目标更近的方向移动。然而，城中部分格子安装了传送装置：一旦 Alice 踏入这样的格子，她就会立即被送回起点，只能重新开始旅程。

Alice 在岔路口会依据一枚有偏硬币决定方向。请你计算，在她最终抵达终点之前，期望会被传送回起点多少次。

题目描述

网格城共有 $R$ 行、$C$ 列，行和列均从 $0$ 开始编号。

部分格子为空地，部分格子中有传送器。每个传送器都会把进入该格子的人立即传送到起点 $(0,0)$。

Alice 初始位于 $(0,0)$，目标是到达 $(R-1,C-1)$。她始终遵循以下规则移动：

• 每一步只能移动到与当前格子相邻、且更接近目标的格子；
• 因此，从一般位置 $(i,j)$ 出发，她只可能移动到 $(i+1,j)$ 或 $(i,j+1)$；
• 当只有一个方向仍在网格内时，她必定沿该方向移动；
• 当两个方向都可行时，令

$$p=\frac{p_{\mathrm{num}}}{p_{\mathrm{den}}}.$$

她以概率 $p$ 向下移动到 $(i+1,j)$，以概率 $1-p$ 向右移动到 $(i,j+1)$。

若 Alice 进入传送器格子，她会立刻回到 $(0,0)$，随后继续按相同规则行动。

请计算 Alice 在第一次到达终点之前，被传送回起点的期望次数。

若 Alice 到达终点的概率为 $0$，输出 -1。

输入格式

第一行包含四个整数 $R,C,p_{\mathrm{num}},p_{\mathrm{den}}$。

接下来 $R$ 行，每行包含一个长度为 $C$ 的字符串，描述网格：

• . 表示空地；
• T 表示传送器。

输出格式

输出一个实数，表示 Alice 在第一次到达终点之前被传送回起点的期望次数。

若 Alice 无法到达终点，输出 -1。

当答案为实数时，若你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

数据范围

• $2\le R,C\le 20$；
• $2\le p_{\mathrm{den}}\le 1000$；
• $1\le p_{\mathrm{num}}<p_{\mathrm{den}}$；
• 网格中的字符只可能是 . 或 T；
• 起点 $(0,0)$ 和终点 $(R-1,C-1)$ 一定是空地。

样例 1

输入

2 2 1 2
..
..

输出

0.0

说明

网格中没有传送器，因此 Alice 一定可以直接到达终点，期望传送次数为 $0$。

样例 2

输入

2 2 1 2
.T
..

输出

1.0

说明

Alice 在起点以相同概率向下或向右。向下会成功到达终点，向右会触发传送器。每次尝试成功和失败的概率均为 $1/2$，故期望失败次数为 $1$。

样例 3

输入

2 2 46 47
.T
..

输出

0.021739130434782705

说明

地图与样例 2 相同，但 Alice 几乎总是向下移动，因此触发传送器的期望次数显著降低。

样例 4

输入

3 7 2 3
.....T.
....T..
T..T...

输出

-1.0

说明

Alice 每次尝试都会在到达终点前进入某个传送器，因此到达终点的概率为 $0$。

样例 5

输入

5 6 3 7
....T.
...TT.
.T....
...T..
......

输出

5.417334860633832

说明

部分传送器位于 Alice 永远不会经过的位置，它们不会影响答案。