Problem Description

This problem is translated from PA 2022 Round 5 Wieczór gier.

Bytie likes to play his favorite board game in the evening. Fortunately, this game is single-player, so Bytie does not need to play it with friends.

The board has $n$ rows and each row has $m$ cells, so there are $nm$ cells in total. There are $k$ indistinguishable pieces on the board, with at most $8$ pieces. The edge of the board has decorative marks that indicate the up, down, left, and right directions. Each cell may be empty or contain one piece, but there is always at least one piece on the board, and at least one cell is empty. In other words, $1\le k\le nm-1$.
A move in the game is: choose a cell that contains a piece and an adjacent cell (sharing an edge) that is empty, then move the piece into the adjacent empty cell.

Bytie likes these simple but exciting rules and can spend hours moving pieces. One evening, he sat in front of the board, placed $k$ pieces on it, and came up with a target arrangement of the pieces, which may be different from the initial one. He said that every time he is about to make a move, he will list all possible moves for all pieces in the current position, and then randomly choose one move among them. For example, if there are two pieces on the board, the first piece has one possible move and the second piece has two possible moves, then Bytie will choose one of these three moves with probability $\frac{1}{3}$ to make the next move.

Bytie (as we already mentioned) really likes playing this game, so he has decided that he will make exactly $100^{100^{100^{100}}}$ moves. After making so many moves, what is the probability that the arrangement of pieces on the board is the same as the target arrangement?

Input Format

The first line contains two integers $n,m$, representing the number of rows and columns of the board.

The next $n$ lines each contain $m$ characters, describing the initial board configuration. If the character in row $i$ and column $j$ is ., then the cell at row $i$, column $j$ is empty. Otherwise, the character is O (uppercase letter o), meaning there is a piece in the cell at row $i$, column $j$.

Then there is a blank line, and then the next $n$ lines describe the target state, in the same format as the initial state.

It is guaranteed that the two boards have the same number of pieces, and that this number is in the range $[1,nm-1]$. Also, it is guaranteed that the number of pieces does not exceed $8$.

Output Format

Output one real number on one line, representing the probability that after exactly $100^{100^{100^{100}}}$ moves, the arrangement of pieces on the board is the same as the target arrangement. The output will be considered correct if the absolute error does not exceed $10^{-13}$.

Note: Due to technical reasons, if you output more than $18$ digits after the decimal point, or output a decimal in scientific notation, it will be judged as “Wrong Answer”.

1 5
O....

....O

0.25

2 2
O.
.O

OO
..

0

Hint

For $100\%$ of the testdata, it holds that:

$1\le n,m\le 8$。

Translated by ChatGPT 5