Bacterial Colony Experiment

Professor Albert Bynstein is studying a new strain of bacteria, code‐named Algorithmic Proeliis. He sets up a large rectangular experimental board divided into n × m regions arranged in n rows and m columns.

For each region, the professor makes one of three decisions:

• He definitely places a Petri dish in the region.
• He definitely leaves the region empty.
• He flips a fair coin to determine whether to place a dish (heads means a dish is placed, tails means the region is left empty).

After placing the dishes, he chooses a positive integer k and puts exactly k bacteria into every Petri dish that was placed.

The experiment then proceeds as follows. As long as there exists at least one pair of adjacent (sharing a common edge) non‐empty dishes, one such pair is chosen uniformly at random and one bacterium in each of the two dishes dies. The process repeats until no pair of adjacent dishes both contain at least one bacterium.

Let f(k) denote the expected number of bacteria surviving at the end of the experiment (the expectation is taken over both the coin toss decisions for dish placement and the random choice of adjacent pairs during the experiment). It can be shown that the limit $$ \lim_{k\to \infty} \frac{f(k)}{k} $$ exists as a mysterious number. In fact, one may prove that when k is huge the surviving bacteria in each dish are either almost all lost (i.e. the dish is effectively emptied) or remain full (all k bacteria survive). Therefore the limit equals the maximum number of dishes that can be "saved" – that is, the maximum independent set in the graph defined on the board where vertices correspond to regions with a dish and edges connect adjacent regions. (Remember that in any final configuration no two adjacent dishes can both be non–empty.)

More precisely, let the board configuration be determined as follows:

• For a region marked 1 the professor definitely places a dish.
• For a region marked 0 no dish is placed.
• For a region marked ? the professor tosses a fair coin; on heads a dish is placed, on tails not.

Your task is to compute the expected value of $$ \lim_{k\to \infty} \frac{f(k)}{k} = E\Bigl[|\text{Maximum Independent Set}| \Bigr] $$ over the randomness of the coin tosses, and express it in the form of an irreducible fraction p/q.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10), representing the number of rows and columns respectively.

Each of the following n lines contains a string of length m. Each character is either:

• '1' indicating a dish is definitely placed,
• '0' indicating no dish is placed, or
• '?' indicating a coin toss decision (dish is placed with probability 1/2).

outputFormat

Output a single line with the expected value of lim_k→∞ f(k)/k as an irreducible fraction in the form p/q (without spaces).

sample

1 1
1

1/1