题目描述

题目译自 PA 2022 Runda 5 Wieczór gier

Bytie 喜欢在晚上玩他最喜欢的棋盘游戏。幸运的是，这个游戏是单人游戏，Bytie 不需要和朋友一起玩这个游戏。

棋盘共 $n$ 行，每行有 $m$ 个方格，整个棋盘共有 $nm$ 个方格。棋盘上有 $k$ 个无法区分的棋子，最多只有 $8$ 个。 棋盘的边缘有装饰性的标记，这些标记表明了棋盘的上下左右方位。每个方格可能是空的，也可能放有一个棋子，但棋盘上总是至少有一个棋子，而且至少有一个方格是空的。换句话说，满足 $1\le k\le nm-1$。游戏中一步棋指的是选择一个包含棋子的方格和与之相邻的另一个不包含棋子的方格，然后将棋子从这个方格移到相邻的空方格中。

Bytie 喜欢这个不复杂但令人兴奋的规则，他可以花几个小时来移动棋子。一天晚上，他坐在棋盘前，在棋盘上摆了 $k$ 个棋子，并想到了一种棋子的排布方式，这种排布方式也许与开始时不同。他说，每次他要走一步棋时，他都会确定现在所有棋子的所有可能走法，并从这些走法中随机选出他要怎么走棋。例如，如果棋盘上有两个棋子，第一个棋子有一种走法，第二个棋子有两种走法，那么 Bytie 将以 $\frac{1}{3}$ 的概率从这三种走法中选出一种来走下一步棋。

Bytie（正如我们已经提到的）非常喜欢玩这个游戏，所以他已经确定他会正好走 $100^{100^{100^{100}}}$ 步棋。在走了这么多步之后，棋盘上的棋子排布和目标排布相同的概率是多少？

输入格式

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

接下来 $n$ 行，每行 $m$ 个字符，表示初始的棋盘排布。如果第 $i$ 行第 $j$ 个字符是 .，那么棋盘第 $i$ 行第 $j$ 列的方格是空的。否则，这个字符将是 O（大写的 o），表示第 $i$ 行第 $j$ 列的方格中有一个棋子。

接下来空一行，再接下来 $n$ 行描述目标状态，格式如初始状态。

保证两个棋盘上的棋子个数相同，并且这个个数属于区间 $[1,nm-1]$。此外，保证棋子数不超过 $8$。

输出格式

输出一行一个实数，表示在恰好走了 $100^{100^{100^{100}}}$ 步棋后，棋盘上的棋子排布和目标排布相同的概率。如果输出与答案的绝对误差不超过 $10^{-13}$，那么输出将被认为是正确的。

注意：由于技术原因，输出小数点后位数多于 $18$ 位，或输出科学计数法形式的小数均将被判为「答案错误」。

1 5
O....

....O

0.25

2 2
O.
.O

OO
..

0