Problem Description

This problem is translated from PA 2022 Round 5 Bakterie.

Professor Albert Bynstein is currently studying a newly discovered strain of bacteria, and he gave it the codename Algorithmic Proeliis. In his next experiment, he prepared a large rectangular lab bench and divided it into $n \cdot m$ cells arranged into $n$ rows, with $m$ cells in each row.

Then, for each cell, the professor will choose one of three options: either he will definitely place a petri dish there, or he will definitely not place a petri dish there, or he will flip a fair coin to decide whether to place a petri dish. Once all petri dishes have been placed, to carry out the experiment he needs to choose a positive integer $k$ and put exactly $k$ bacteria into each petri dish.

These bacteria are very hostile to other colonies, so the experiment proceeds as follows: as long as there exists a pair of adjacent non-empty petri dishes, one such pair is selected at random (with a uniform probability distribution), and then one bacterium in each of the two petri dishes dies. We assume that two cells are adjacent if and only if they share a common side.

Taking into account the randomness from placing petri dishes in some cells by coin flips, and the randomness from selecting adjacent petri dishes and killing bacteria in them, let $f(k)$ be the expected number of bacteria that survive after the whole experiment. Clearly, the experiment ends when there is no longer any pair of adjacent petri dishes that both contain at least one bacterium.

Putting a few bacteria into each dish is hard, but putting a lot of bacteria at once is much easier. Therefore, the professor thought for a while and then wrote the following expression on the blackboard:

As his assistant, your task is to compute the value of the limit above. It can be proven that this value is always a rational number, so you need to output it as an irreducible fraction.

Input Format

The first line contains two integers $n, m$, denoting the size of the rectangular lab bench.

The next $n$ lines describe the lab bench. The $i$-th line contains $m$ characters, and the $j$-th character is denoted by $a_{i,j}$. If $a_{i,j}$ is ., then the cell in row $i$ and column $j$ will definitely not have a petri dish. If $a_{i,j}$ is O (uppercase letter o), then the cell in row $i$ and column $j$ will definitely have a petri dish. If $a_{i,j}$ is ?, then the cell in row $i$ and column $j$ will be decided by a coin flip whether to place a petri dish.

Output Format

Output one line, the answer to the professor’s question. Print it in the form $a/b$, where $b \ge 1$ and $\gcd(a,b)=1$.

4 5
O...O
?OO.?
.OOO.
?..O.

5/2

Hint

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

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

Translated by ChatGPT 5