{"raw_statement":[{"iden":"background","content":"2020 年 6 月的某一天，小 A 在等待网络加载的过程中打开了扫雷，从此便一发不可收拾。\n\n小 A 是一个任何事都喜欢做到极致的人，玩游戏也不例外：他不惜花费大量时间不断尝试打破记录。一个个夜晚就在熟练的 `Alt + G + N` 中过去了。\n\n> “这把有戏，前五十个雷只用了不到四十五秒”。他心里想着，紧握鼠标的手微微颤抖。\n>\n> “快，快，快 …… 还有最后二十个雷 ……”。\n>\n> 游戏的关键时刻，他难以按捺激动的心情。直到他遇到了二选一。\n>\n> 他愣了一下，随后迅速按下最后两块空地当中的一个。\n> \n> 一束横贯屏幕的白色激光缓缓扫过，他知道自己打破了记录 …… [整整十二秒](https://cdn.luogu.com.cn/upload/image_hosting/1seixkiz.png)！巨大的惊喜让他跳了起来。\n>\n> 2020.6.19"},{"iden":"statement","content":"以下是简化后的扫雷游戏规则：\n\n- 定义连通为 **八连通**。\n- 如果打开雷，所有雷 **全部同时爆炸**，游戏结束。\n- 如果打开空地，若其周围没有雷，则递归打开周围八个方块。\n- [如图](https://cdn.luogu.com.cn/upload/image_hosting/kjjqs2v1.png)，点开任意红色框内方块均形成当前局面。\n\n\n给定一张 $n\\times m$ 的初始地图。小 A 决定搜出所有可能的局面，并找到最优鼠标点击顺序，从而速通这张地图。\n\n为设置合适的数组大小，小 A 需要知道有多少种不同局面。对 $998244353$ 取模。\n\n- 如果方块是雷，它有爆炸和未爆炸两种状态；如果方块是空地，它有打开和未打开两种状态。\n- 两个局面不同，当且仅当存在方块状态不同。\n- 保证周围无雷的空地形成不超过 $37$ 个连通块。"},{"iden":"input","content":"第一行一个整数 $S$，表示该测试点的 Subtask 编号。\n\n第二行两个整数 $n, m$。\n\n接下来 $n$ 行，每行一个长度为 $m$ 的字符串描述地图，其中 $\\texttt{.}$ 表示方块无雷，$\\texttt{*}$ 表示方块有雷。"},{"iden":"output","content":"一行一个整数表示答案。"},{"iden":"note","content":"**「样例解释」**\n\n用 `.` 表示未打开的方块，`+` 表示打开的方块，`*` 表示未爆炸的雷，`!` 表示爆炸的雷。\n\n样例 1 的所有 4 种局面为 `.*   +*   .!   +!`。\n\n样例 2 的所有 20 种局面为\n```plain\n0\n..*\n...\n   \n1\n++*  .+*  ..!  ..*  ..*\n++.  ...  ...  .+.  ..+  \n   \n2\n++!  ++*  .+!  .+*  .+*  ..!  ..!  ..*\n++.  +++  ...  .+.  ..+  .+.  ..+  .++\n   \n3\n++!  .+!  .+!  .+*  ..!\n+++  .+.  ..+  .++  .++\n   \n4\n.+!\n.++\n```\n\n数字描述了最少点击次数。\n\n**「数据范围与约定」**\n\n**本题采用捆绑测试。**\n\n设周围无雷的空地形成 $d$ 个连通块。\n\n- Subtask #1（15 points）：$nm\\leq 21$。\n- Subtask #2（4 points）：地图中只有一个雷。\n- Subtask #3（5 points）：$d = 0$。\n- Subtask #4（6 points）：$d = 1$。\n- Subtask #5（7 points）：$d = 2$。\n- Subtask #6（8 points）：$d \\leq 17$。依赖 Subtask #1，#2，#3，#4，#5。\n- Subtask #7（9 points）：$d \\leq 23$。依赖 Subtask #6。\n- Subtask #8（16 points）：$d\\leq 27$。依赖 Subtask #7。\n- Subtask #9（17 points）：$d\\leq 33$。依赖 Subtask #8。\n- Subtask #10（13 points）：无特殊限制。依赖 Subtask #9。\n\n对于 $100\\%$ 的数据：\n\n- $1\\leq n, m\\leq 500$。\n- $0\\leq d\\leq 37$。\n- **不保证** 地图中有雷或空地。\n\n**「题目来源」**\n\n- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) D\n- Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。\n- Tester：[chenxia25](https://www.luogu.com.cn/user/138400) & [asmend](https://www.luogu.com.cn/user/21658)。\n\n感谢 [Elegia](https://www.luogu.com.cn/user/21423) 对本题做出的贡献。"}],"translated_statement":null,"sample_group":[["0\n1 2\n.*","4"],["0\n2 3\n..*\n...","20"],["0\n4 4\n..*.\n.*..\n*...\n....","2112"],["0\n7 6\n..*...\n......\n*...**\n......\n..*...\n......\n......","5041530"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}