Description

以下是简化后的扫雷游戏规则：

• 定义连通为 八连通。
• 如果打开雷，所有雷 全部同时爆炸，游戏结束。
• 如果打开空地，若其周围没有雷，则递归打开周围八个方块。
• 如图，点开任意红色框内方块均形成当前局面。

给定一张 $n\times m$ 的初始地图。小 A 决定搜出所有可能的局面，并找到最优鼠标点击顺序，从而速通这张地图。

为设置合适的数组大小，小 A 需要知道有多少种不同局面。对 $998244353$ 取模。

• 如果方块是雷，它有爆炸和未爆炸两种状态；如果方块是空地，它有打开和未打开两种状态。
• 两个局面不同，当且仅当存在方块状态不同。
• 保证周围无雷的空地形成不超过 $37$ 个连通块。

Input Format

第一行一个整数 $S$，表示该测试点的 Subtask 编号。

第二行两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串描述地图，其中 $\texttt{.}$ 表示方块无雷，$\texttt{*}$ 表示方块有雷。

Output Format

一行一个整数表示答案。

0
1 2
.*

4

0
2 3
..*
...

20

0
4 4
..*.
.*..
*...
....

2112

0
7 6
..*...
......
*...**
......
..*...
......
......

5041530

Hint

「样例解释」

用 . 表示未打开的方块，+ 表示打开的方块，* 表示未爆炸的雷，! 表示爆炸的雷。

样例 1 的所有 4 种局面为 .* +* .! +!。

样例 2 的所有 20 种局面为

0
..*
...
   
1
++*  .+*  ..!  ..*  ..*
++.  ...  ...  .+.  ..+  
   
2
++!  ++*  .+!  .+*  .+*  ..!  ..!  ..*
++.  +++  ...  .+.  ..+  .+.  ..+  .++
   
3
++!  .+!  .+!  .+*  ..!
+++  .+.  ..+  .++  .++
   
4
.+!
.++

数字描述了最少点击次数。

「数据范围与约定」

本题采用捆绑测试。

设周围无雷的空地形成 $d$ 个连通块。

• Subtask #1（15 points）：$nm\leq 21$。
• Subtask #2（4 points）：地图中只有一个雷。
• Subtask #3（5 points）：$d = 0$。
• Subtask #4（6 points）：$d = 1$。
• Subtask #5（7 points）：$d = 2$。
• Subtask #6（8 points）：$d \leq 17$。依赖 Subtask #1，#2，#3，#4，#5。
• Subtask #7（9 points）：$d \leq 23$。依赖 Subtask #6。
• Subtask #8（16 points）：$d\leq 27$。依赖 Subtask #7。
• Subtask #9（17 points）：$d\leq 33$。依赖 Subtask #8。
• Subtask #10（13 points）：无特殊限制。依赖 Subtask #9。

对于 $100\%$ 的数据：

• $1\leq n, m\leq 500$。
• $0\leq d\leq 37$。
• 不保证 地图中有雷或空地。

「题目来源」

• Sweet Round 8 D
• Idea & Solution：Alex_Wei。
• Tester：chenxia25 & asmend。

感谢 Elegia 对本题做出的贡献。