YY 方阵

时间限制：3s
空间限制：512MB

题目描述

给定一个 $H$ 行 $W$ 列的字符网格，每个格子中是 X 或 Y。从左上角 $(1,1)$ 出发，每次只能向下或向右移动一格，直到到达右下角 $(H,W)$。把一条路径经过的字符依次连接成字符串，设其中相邻两个字符均为 Y 的位置共有 $k$ 个，则这条路径的得分为 $k^2$。

求所有从 $(1,1)$ 到 $(H,W)$ 的合法路径的得分之和，对 $998244353$ 取模。

输入格式

第一行两个整数 $H,W$。接下来 $H$ 行，每行一个长度为 $W$、只由 X 和 Y 组成的字符串，描述网格。

输出格式

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

样例输入 1

2 2
YY
XY

样例输出 1

4

样例输入 2

2 2
XY
YY

样例输出 2

2

样例解释

样例一中两条路径对应的字符串分别为 YYY 和 YXY，得分分别为 $4$ 和 $0$。

数据范围

• $1\le H,W\le 2000$；
• 每行字符串长度均为 $W$，且只包含 X 与 Y。