题目描述

题目译自 PA 2022 Runda 5 Bakterie

Albert Bynstein 教授目前正在研究一种新发现的细菌菌株，他给它起了一个代号叫 Algorithmic Proeliis。在他的下一个实验中，他准备了一个大的矩形实验台，他将其分为 $n\cdot m$ 个区域，排列成 $n$ 行，每行 $m$ 个区域。

然后对于每个区域，教授将从三个选项中选择一个：要么他一定会在其中放置一个培养皿，要么他一定不放培养皿，要么他将抛出一枚均匀的硬币来决定放不放培养皿。一旦培养皿放置完毕，为了进行实验就需要选择一个正整数 $k$，并在每个培养皿里放置恰好 $k$ 个细菌。

这种细菌的特点是十分敌视其他菌落，因此实验过程如下：只要有一对相邻的、非空的培养皿，就会随机选出一对这样的培养皿（概率分布相等），之后两个培养皿中各有一个细菌死亡。我们假定，当且仅当两个培养皿所处的区域有一条公共边时，两区域相邻。

考虑到抛硬币决定将培养皿放在某些区域里的随机性，和选择相邻培养皿并让其中的细菌死亡的随机性，令 $f(k)$ 表示在整个实验中存活的细菌的期望数量。显然，当不再有一对相邻的培养皿各含有至少一个细菌时，实验就会结束。

一次在培养皿里放几个细菌很难，但一次性放置很多细菌就会容易得多。为此，教授沉思了一下，然后在黑板上写下了如下表达式：

你作为他的助手，任务是计算上述极限的值。可以证明这个值总是一个可测的数字，所以你需要用一个不可约分数的形式表达这个值。

输入格式

输入第一行包含两个整数 $n,m\ (1\le n,m\le 200)$，表示这个矩形实验台的大小。

接下来 $n$ 行描述试验台。第 $i$ 行包含 $m$ 个字符，第 $j$ 个字符记为 $a_{i,j}$。如果 $a_{i,j}$ 是 .，则第 $i$ 行的第 $j$ 个区域一定不放培养皿。如果 $a_{i,j}$ 是 O（大写的 o），则第 $i$ 行的第 $j$ 个区域一定放培养皿。如果 $a_{i,j}$ 是 ?，则第 $i$ 行的第 $j$ 个区域会用投硬币的方式决定放不放培养皿。

输出格式

输出一行，表示对教授问题的回答。按 $a/b$ 的形式输出，其中 $b\ge 1$ 且 $\gcd(a,b)=1$。

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

5/2

数据范围与提示

• 某些子任务满足不存在字符 ?。
• 某些子任务满足最多存在 $5$ 个字符 ?。
• 某些子任务满足 $n\le 1$。
• 某些子任务满足 $n\le 2$。
• 某些子任务满足 $n,m\le 25$。
• 某些子任务满足如果 $(i\cdot j)$ 的值能被 $5$ 整除，则 $a_{i,j}$ 是 .。

对于上面提到的每种情况，都存在至少一个子任务满足。这些子任务满足条件可能不相交，也可能相交。