AT_awtf2026algo_e Even Rows

有一个大小为 $N$ 行 $M$ 列的棋盘。我们将第 $i$ 行从上到下、第 $j$ 列从左到右的格子称为 $(i, j)$。 每个格子要么为空，要么有一个棋子。棋盘的状态由 $N$ 个长度为 $M$ 的字符串 $S_1, S_2, \ldots, S_N$ 给出：如果 $S_i$ 的第 $j$ 个字符是 `.`，表示格子 $(i, j)$ 为空；如果是 `O`，表示格子 $(i, j)$ 上有一个棋子。 对于整数 $L$ 和 $R$（$1 \leq L \leq R \leq N$），定义 $f(L, R)$ 如下： - 提取棋盘的第 $L$ 行到第 $R$ 行，得到一个有 $R-L+1$ 行的新棋盘 $X$。 - 你可以对 $X$ 执行如下操作若干次（可以为零次）： - 任选一个棋子，将其移动到与其相邻（上、下、左或右）的格子。这里，目标格子必须没有其他棋子，并且不能把棋子移动到 $X$ 的外面。 - 你的目标是使 $X$ 的每一行中棋子的数量均为偶数。如果无法达成目标，设 $f(L, R)=0$；如果能达成目标，$f(L, R)$ 为实现目标所需的最少操作次数。 请计算 $\sum_{1 \leq L \leq R \leq N} f(L, R)$ 模 $998244353$ 的结果。 对于每个输入，共有 $T$ 组测试数据。

输入从标准输入读入，格式如下： > $T$ > $case_1$ > $case_2$ > $\vdots$ > $case_T$ 每组测试数据格式如下： > $N$ $M$ > $S_1$ > $S_2$ > $\vdots$ > $S_N$

对于每组测试数据，输出一行结果。

### 样例解释 1 在第一个测试样例中，各 $f(L, R)$ 的值如下： - $f(1,1)=0$ - $f(1,2)=2$ - $f(1,3)=0$ - $f(2,2)=0$ - $f(2,3)=1$ - $f(3,3)=0$ ### 数据范围 - $1 \leq T \leq 250000$ - $2 \leq N \leq 500000$ - $2 \leq M \leq 10$ - $S_i$ 是长度为 $M$ 的字符串，仅包含 `.` 和 `O`。 - 所有测试数据中 $N$ 的总和不超过 $500000$。 由 ChatGPT 5 翻译