Description

网瘾少女 yyjj 今天也在玩游戏，游戏地图是一个由小写英文字母 $\texttt{x}$ 和 $\texttt{y}$ 构成的一个 $r$ 行 $c$ 列的矩阵，她要从矩阵的左上角 $(1,1)$ 走到矩阵的右下角 $(r,c)$，由于她想快点到目的地，她只会往右或往下走。

yyjj 走过的路径可以看成是由若干段 $\texttt{x}$ 和若干段 $\texttt{y}$ 交替拼接而成的字符串，一条路径的 yy 能量是该条路径所有 $\texttt{y}$ 段的长度的平方和。比如，字符串 $\texttt{xxyyyxyxyy}$ 的 yy 能量为：$3^2 + 1^2 + 2^2 = 14$。

yyjj 想知道所有能从 $(1,1)$ 到达 $(r,c)$ 的路径的 yy 能量的和。请输出该答案对 $998244353$ 取模后的值。

Format

Input

第一行两个正整数 $r$ 和 $c$ $(1\le r,c\le 2000)$，分别表示矩阵的行数和列数。

接下来 $r$ 行，每行一个长为 $c$ 的只包含 $\texttt{x}$ 和 $\texttt{y}$ 的字符串，表示游戏地图。

Output

输出一个整数，表示所有从 $(1,1)$ 到 $(r,c)$ 的路径的 yy 能量的和对 $998244353$ 取模后的值。

Samples

2 2
xy
yy

8

3 3
xxx
yxx
xxy

9

Note

对于第二组样例，路径分别是：$\texttt{xyxxy, xyxxy, xyxxy, xxxxy, xxxxy, xxxxy}$。

所有路径的 yy 能量和为：$(1+1)\times 3+1\times 3=9$。

Limitation

1s, 1024KiB for each test case.