Bajtek 喜欢在晚上玩他最喜欢的棋盘游戏。幸运的是，这是一个单人游戏，Bajtek 不需要朋友也能享受游戏的乐趣。

游戏套装包含一个被划分为 $n \times m$ 个方格的棋盘，以及 $k$ 个不可区分的棋子，其中 $k$ 最多为 8。棋盘边缘有装饰性标记，因此总是可以区分上下左右。每个方格可以是空的，也可以包含一个棋子，且棋盘上始终至少有一个棋子，至少有一个空位。换句话说，$1 \le k \le nm - 1$。游戏中的移动方式是：选择一个包含棋子的方格，以及一个与其相邻（共享边）且不包含棋子的方格，然后将棋子从第一个方格移动到第二个方格。

Bajtek 喜欢简单但令人兴奋的游戏规则，他可以花很长时间移动棋子。一天晚上，他坐在棋盘前，摆放了 $k$ 个棋子，并构思了一个目标棋子布局（可能与初始布局不同）。他决定，每次需要移动时，他会确定当前所有可能的移动集合，并从中随机选择一个执行。例如，如果棋盘上有两个棋子，第一个棋子可以进行 1 种移动，第二个棋子可以进行 2 种移动，那么 Bajtek 将以 $\frac{1}{3}$ 的概率执行这三种移动中的任意一种。

Bajtek 非常喜欢玩这个游戏，因此他决定总共执行 $100^{100^{100^{100}}}$ 次移动。请问在执行这么多步移动后，棋盘上的棋子处于他所选目标布局的概率是多少？

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 8$)，分别表示棋盘的行数和列数。

接下来的 $n$ 行包含 $m$ 个字符，表示棋盘的初始状态。如果第 $i$ 行的第 $j$ 个字符是 ‘.’，则表示该方格为空。否则，该字符为 ‘O’（大写字母 o），表示该方格包含一个棋子。

随后是一个空行，接着是 $n$ 行，以相同的方式描述棋盘的目标状态。

保证两个棋盘包含相同数量的棋子，数量在 $[1, nm - 1]$ 范围内。此外，棋子总数不超过 8 个。

输出格式

输出一行，包含一个实数，表示执行 $100^{100^{100^{100}}}$ 次随机移动后，棋盘达到目标状态的概率。如果绝对误差不超过 $10^{-13}$，则答案将被接受。

注意：由于技术原因，小数点后输出超过 18 位数字或使用科学计数法可能会导致“答案错误”的判决。

样例

输入 1

1 5
O....
....O

输出 1

0.25

输入 2

2 2
O.
.O

OO
..

输出 2

0

说明

样例说明：在第一个样例测试中，棋子最终停在棋盘右侧的概率约为 $\frac{1}{4}$。在第二个样例测试中，棋子交替位于对角线和某一边上，因此不可能在 $100^{100^{100^{100}}}$ 次移动后从初始状态达到目标状态。