题目描述

$H$ 行 $W$ 列のマス目の各マスに X, Y のいずれかの文字が書かれています． 上から $i$ 行目，左から $j$ 列目のマスを $(i,\ j)$ で表します． マス目に書かれている文字は $H$ 個の文字列 $S_1,\ S_2,\ \dots,\ S_H$ によって与えられ，$S_i$ の $j$ 文字目がマス $(i,\ j)$ に書かれた文字を表します．

隣り合う各行および各列の間に，マス目全体を横断（縦断）するように柵を設置できます． 柵同士は交差しても構いません． 柵の設置後に，「あるマスから始めて上下左右に隣接するマスへの移動を繰り返すことで，柵を越えずに到達可能なマス全体」を区画と定義します． （出力例 1 の説明も参考にしてください．）

柵の設置方法は全部で $2^{H-1}\ \times\ 2^{W-1}$ 通りありますが，そのうち次の条件を満たすものの個数を $998244353$ で割った余りを求めてください．

条件: 各区画には Y が書かれたマスがちょうど $2$ 個含まれている．

输入格式

入力は以下の形式で標準入力から与えられる．

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

输出格式

条件を満たす柵の設置方法の総数を $998244353$ で割った余りを出力せよ．

题目大意

Feyn 有一个 $H$ 行 $W$ 列的矩阵，矩阵里面的元素均为字符 $X$ 或 $Y$。Feyn 想要在矩阵中放一些栅栏，栅栏要么放在横着的两行之间，要么放在竖着的两列之间，必须放完整行或整列。容易知道，在不限制栅栏数量的前提下，有 $2^{H-1}\times 2^{W-1}$ 种放栅栏的方案。Feyn 有一些特殊的癖好：他希望栅栏分割出的每个连通块内，都有恰好两个字符 $Y$。请输出上述所有方案中符合条件的方案数，对 $998244353$ 取模。

(translated by 342873)

2 3
XYY
YXY

2

2 3
XYX
YYY

0

2 58
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY

164036797

提示

制約

• $1\ \leq\ H\ \leq\ 2000$
• $1\ \leq\ W\ \leq\ 2000$
• $S_i\ (1\ \leq\ i\ \leq\ H)$ は X, Y からなる長さ $W$ の文字列である．

Sample Explanation 1

柵の設置方法として，以下の $8$ 通りがあります． X Y Y X|Y Y X Y|Y X|Y|Y | | | | Y X Y Y|X Y Y X|Y Y|X|Y X Y Y X|Y Y X Y|Y X|Y|Y ----- -+--- ---+- -+-+- Y X Y Y|X Y Y X|Y Y|X|Y たとえば，$2,\ 3$ 列目の間に柵を設置した場合，区画は XY YX Y Y であり，それぞれにちょうど $2$ 個の Y が含まれているので，条件を満たします． また，$1,\ 2$ 行目の間と $1,\ 2$ 列目の間に柵を設置した場合，区画は X YY Y XY となり，$2$ つ目の区画以外にはちょうど $2$ 個の Y が含まれていないので，条件を満たしません．

Sample Explanation 2

どのように柵を設置しても条件を満たしません．

Sample Explanation 3

条件を満たす柵の設置方法の総数を $998244353$ で割った余りを出力してください．