AT_arc157_c [ARC157C] YY Square

在一个 $H$ 行 $W$ 列的网格中，每个格子上写有字符 `X` 或 `Y`。从上往下第 $i$ 行，从左往右第 $j$ 列的格子记作 $(i, j)$。网格中的字符由 $H$ 个字符串 $S_1, S_2, \dots, S_H$ 给出，第 $i$ 个字符串 $S_i$ 的第 $j$ 个字符表示格子 $(i, j)$ 上的字符。 从格子 $(1, 1)$ 出发，每次只能向下或向右移动，最终到达格子 $(H, W)$。对于一条这样的路径 $P$： - 用 $ \mathrm{str}(P) $ 表示按照路径 $P$ 经过的格子上的字符依次拼接得到的、长度为 $H + W - 1$ 的字符串； - 定义路径 $P$ 的**得分**为 $ \mathrm{str}(P) $ 中相邻的 `Y` 字符对的**个数的平方**。 所有可能的路径 $P$ 的数量为 $ \displaystyle\binom{H + W - 2}{H - 1} $。请计算所有可能路径的得分之和，并对 $998244353$ 取模。 其中，$ \displaystyle\binom{N}{K} $ 表示从 $N$ 个不同元素中选出 $K$ 个的组合数（二项式系数）。

输入按以下格式从标准输入给出： > $H$ $W$ > $S_1$ > $S_2$ > $\vdots$ > $S_H$

输出所有可能路径的得分之和对 $998244353$ 取模的结果。

### 限制条件 - $1 \leq H \leq 2000$ - $1 \leq W \leq 2000$ - $S_i$（$1 \leq i \leq H$）是仅由 `X` 和 `Y` 组成的、长度为 $W$ 的字符串。 ### 样例解释 1 所有可能的路径 $P$ 有 $(1, 1) \to (1, 2) \to (2, 2)$ 和 $(1, 1) \to (2, 1) \to (2, 2)$ 两种： - 对于 $(1, 1) \to (1, 2) \to (2, 2)$，$\mathrm{str}(P) = $`YYY`，第 $1, 2$ 个字符和第 $2, 3$ 个字符各有一对相邻的 `Y`，共 $2$ 处，因此得分为 $2^2 = 4$。 - 对于 $(1, 1) \to (2, 1) \to (2, 2)$，$\mathrm{str}(P) = $`YXY`，没有相邻的 `Y`，得分为 $0^2 = 0$。 所以总和为 $4 + 0 = 4$。 ### 样例解释 2 两条路径的 $\mathrm{str}(P)$ 都是 `XYY`，得分均为 $1^2 = 1$。 ### 样例解释 3 请输出所有路径得分之和对 $998244353$ 取模的结果。 由 ChatGPT 4.1 翻译