P15781 [JAG 2025 Summer Camp #3] Grid Painting

有一个 $H \times W$ 的网格，初始时每个单元格都被涂成白色。令 $C_{i,j}$（$1 \leq i \leq H$，$1 \leq j \leq W$）表示从上往下第 $i$ 行、从左往右第 $j$ 列单元格的颜色。 你可以通过任意顺序、任意多次地重复以下两种操作来涂色网格。 **操作 1：** 仅当网格的最右列全为白色时，才能应用此操作。 首先，将整个网格循环右移一列（即，对于所有 $1 \leq i \leq H$，$1 \leq j \leq W$，同时用 $C_{i, j}$ 替换 $C_{i, (j \mod W) + 1}$）。 然后，选择 $1 \leq l \leq r \leq H$，并将 $C_{l, 1}, C_{l+1, 1}, \ldots, C_{r, 1}$ 涂成黑色。 **操作 2：** 仅当网格的最底行全为白色时，才能应用此操作。 首先，将整个网格循环下移一行（即，对于所有 $1 \leq i \leq H$，$1 \leq j \leq W$，同时用 $C_{i, j}$ 替换 $C_{(i \mod H) + 1, j}$）。 然后，选择 $1 \leq l \leq r \leq W$，并将 $C_{1, l}, C_{1, l+1}, \ldots, C_{1, r}$ 涂成黑色。 给定执行若干次操作后的最终网格，请确定能够产生该网格的操作序列的数量。由于答案可能非常大，请输出其对 $998244353 = 119 \times 2^{23} + 1$ 取模的结果。 如果两个操作序列长度不同，或者在任意步骤中移动方向或涂黑的区间不同，则认为它们是不同的。 :::align{center}  :::

输入包含多个测试用例。 第一行包含一个整数 $T$（$1 \leq T \leq 100$），表示测试用例的数量。 接下来是 $T$ 个测试用例。每个测试用例的格式如下： $$ \begin{aligned} & H \ W \\ & S_1 \\ & \vdots \\ & S_H \end{aligned} $$ 对于每个测试用例，第一行包含两个整数 $H$（$1 \leq H \leq 100$）和 $W$（$1 \leq W \leq 100$），分别表示网格的高度和宽度。 接下来的 $H$ 行，每行包含一个长度为 $W$ 的字符串 $S_i$，表示最终网格，仅由字符 ‘#’ 和 ‘.’ 组成。如果 $S_i$ 的第 $j$ 个字符是 ‘#’，则 $C_{i,j}$ 为黑色；如果是 ‘.’，则为白色。

每个测试用例输出一行：可能的操作序列数量对 $998244353$ 取模的结果。

翻译由 DeepSeek V3.2 完成