問題文

$N$ 行 $M$ 列のグリッドがあります。 グリッドの $i$ 行目 $j$ 列目を $(i,j)$ と呼ぶことにします。

$S_{i,j}$ が # ならば $(i,j)$ にはマスがあり、. ならば $(i,j)$ にはマスがありません。

また、各マスは正方形であり、異なるマス同士の境界は直線で区切られています。

あなたは全てのマスそれぞれについて、以下の $4$ つのうちいずれか $1$ つの操作を選びます。

• マスの左上と右下を結ぶ対角線を $1$ 本書く。
• マスの左下と右上を結ぶ対角線を $1$ 本書く。
• 上記の $2$ つの対角線をどちらも書く。
• 対角線を書かない。

操作後のマスは下図のいずれかのようになります。

マスの個数を $k$ 個として、グリッド全体に対する線の書き方は全部で $4^{k}$ 通りありますが、以下の条件を満たす線の書き方の数を $998244353$ で割ったあまりを求めて下さい。

• 【条件】線で囲われた図形それぞれを白または黒の $2$ 色で塗り、隣り合う(辺を共有する)図形と色が異なるように塗り分けることができる。

入力

$N$ $M$
$S_{1,1}S_{1,2}\ldots S_{1,M}$
$\vdots$
$S_{N,1}S_{N,2}\ldots S_{N,M}$

• $1 \leq N,M \leq 500$
• $N,M$ は整数
• $S_{i,j}$ は # または .
• # は $1$ つ以上存在する

出力

答えを整数で出力してください。

サンプル

サンプル1

入力

3 4
###.
.###
.##.

出力

16384

入力で与えられるグリッドは左の図のようなマス目です。

例えば、中央の図のような対角線の書き方をすれば、右図のように白と黒で塗り分けることができるため、条件を満たします。

対角線の書き方は全部で $4^8 = 65536$ 通りですが、そのうち条件を満たすのは $16384$ 通りです。

3 3
#.#
.#.
#.#

1024

10 30
####.####..#######.######.#.#.
###.##.#.##.##.##.######.##..#
.#.#.#.#..######.....#..##.##.
##.#..#.###.###..#.###.#######
##.##.#####.####.#..##.#..####
..#####..###########.##.##.##.
######..#...#####..###..##..##
.###..#.##..#..###..#####...##
###..###########.#..##.#...###
#.##.#####.####.####.####.###.

993502162