问题描述

有一个 $H$ 行 $W$ 列的网格，每个方格上都写着字符 X 和 Y。设 $(i, j)$ 表示从上方开始第 $i$ 行第 $j$ 列的方格，网格上的字符由 $H$ 个字符串 $S_1, S_2, \dots, S_H$ 给出：$S_i$ 的第 $j$ 个字符表示方格 $(i, j)$ 上的字符。

对于从方格 $(1, 1)$ 移动到方格 $(H, W)$ 的路径 $P$，定义如下的 分数：

• 设 $\\mathrm{str}(P)$ 是将 $P$ 访问过的方格的字符按访问顺序拼接而成的长度为 $(H + W - 1)$ 的字符串。
• $P$ 的分数是 $\\mathrm{str}(P)$ 中连续出现的 Y 的对数的 平方。

共有 $\\displaystyle\\binom{H + W - 2}{H - 1}$ 条这样的路径。求所有这些路径的分数之和，模 $998244353$。

什么是 $\\binom{N}{K}$？$\\displaystyle\\binom{N}{K}$ 表示从 $N$ 个不同元素中选择 $K$ 个的组合数。

约束条件

• $1 \\leq H \\leq 2000$
• $1 \\leq W \\leq 2000$
• $S_i \\ (1 \\leq i \\leq H)$ 是长度为 $W$ 的由 X 和 Y 构成的字符串。

输入

输入使用以下格式从标准输入给出：

$H$ $W$ $S_1$ $S_2$ $\\vdots$ $S_H$

输出

输出所有可能路径的分数之和，模 $998244353$。

样例一

2 2
YY
XY

样例一输出

4

有两条可能的路径 $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 = 4$。
• 对于 $(1, 1) \\to (2, 1) \\to (2, 2)$，我们有 $\\mathrm{str}(P) = {}$YXY，没有连续的 Y，所以分数是 $0^2 = 0$。

因此，所求的和是 $4 + 0 = 4$。

样例二

2 2
XY
YY

样例二输出

2

对于两条可能的路径 $P$ 中的任何一条，我们有 $\\mathrm{str}(P) = {}$XYY，分数为 $1^2 = 1$。

样例三

10 20
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY

样例三输出

423787835

将分数之和模 $998244353$ 输出。