UOJ Logo Universal Online Judge

UOJ

#422. 【集训队作业2018】小Z的礼物

统计

小Z有一个神奇的自动售货机,里面有 $n \times m$ 种物品,分别放在 $n$ 行 $m$ 列个格子中。每当小Z向自动售货机中投入一枚硬币,他就能获得一对相邻格子中的物品(已经获得的物品可能再次获得),获得每一对相邻格子中的物品的概率是相等的。在这 $n \times m$ 种物品中,有一些物品是小Z喜欢的(小Z喜欢的用 * [星号] 表示,其他的用 .[英文句号] 表示),他想把这些物品包装成一份礼物。小Z想知道,期望投入多少枚硬币后,就可以获得这些他喜欢的物品。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $n$ 行,每行一个长度为 $m$ 的字符串,字符串中仅包含 * 和 . 两种字符。

输出格式

一个整数,表示在模 $998244353$ 意义下的答案。

样例一

input

1 3
***

output

3

样例二

input

3 3
..*
*.*
.*.

output

404051295

限制和约定

对于所有数据,保证 $1 \leq n \leq 6, 2 \leq m \leq 100$。

本题使用捆绑测试。每个子任务有若干个测试点,分为 $5$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

为方便表示,设 $cnt$ 为输入中 * 的数量, $s$ 为由 * 组成的最大连通块(四连通)的大小。

子任务分值限制
110$cnt \leq 6$
220$cnt \leq 20$
320$s \leq 1$
420$s \leq 16$
530无特殊限制

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$