Bajtek likes to spend his evenings playing his favorite board game. Fortunately, this is a single-player game, so Bajtek does not need to have friends to enjoy an engaging session.

The game set consists of a board divided into $nm$ square fields arranged in $n$ rows of $m$ fields each, and $k$ indistinguishable pawns, where $k \le 8$. The board has decorative markings on its edges, so it is always known which side is the bottom, top, left, and right. Each field can be empty or contain a pawn, and it is guaranteed that there is always at least one pawn and at least one empty field on the board. In other words, $1 \le k \le nm - 1$. A move in the game consists of choosing a field containing a pawn and an adjacent field (sharing a side) that does not contain a pawn, and then moving the pawn from the first field to the second.

Bajtek loves the simple yet exciting rules of his game and can spend long hours moving pawns. One evening, while sitting at the board, he placed $k$ pawns on it and came up with a target configuration of pawns, which might be different from the starting one. He decided that every time he makes a move, he will determine the set of all possible moves that can be made at that moment and choose one of them at random. For example, if there are two pawns on the board and Bajtek can make one move with the first pawn and two moves with the second, he will perform each of the three moves with a probability of $\frac{1}{3}$.

Bajtek (as we mentioned) really likes playing this game, so he decided that he will perform exactly $100^{100^{100^{100}}}$ moves. What is the probability that after this many moves, the pawns on the board will be arranged in his chosen target configuration?

Input

The first line of standard input contains two integers $n$ and $m$ ($1 \le n, m \le 8$), representing the number of rows and columns of the board, respectively.

The next $n$ lines contain $m$ characters each, representing the initial state of the board. If the $j$-th character in the $i$-th row is '.', the field in the $j$-th column of the $i$-th row is empty. Otherwise, the character is 'O' (uppercase 'o'), and the field contains a pawn.

Following this, after an empty line, there are $n$ lines that describe the target state of the board in an analogous way.

It is guaranteed that both boards contain the same number of pawns, which is in the range $[1, nm - 1]$. Additionally, there will be at most 8 pawns.

Output

The only line of output should contain a single real number representing the probability that after performing $100^{100^{100^{100}}}$ random moves, we end up in the target state of the board. The answer will be accepted if its absolute error does not exceed $10^{-13}$.

Note: For technical reasons, printing more than 18 digits after the decimal point or printing the result in scientific notation may result in a "wrong answer" verdict.

Examples

Input 1

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

Output 1

0.25

Input 2

2 2
O.
.O

OO
..

Output 2

0

Note

Explanation of examples: In the first example test, the probability that the pawn ends up on the right side of the board is approximately $\frac{1}{4}$. In the second example test, the pawns are alternately placed on one of the diagonals and on one of the sides, so it is impossible to reach the final state from the initial state after $100^{100^{100^{100}}}$ moves.