D - YY Garden Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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 個含まれている．

制約

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

入力

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

H W
S_1
S_2
\vdots
S_H

出力

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

入力例 1

2 3
XYY
YXY

出力例 1

2

柵の設置方法として，以下の 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 が含まれていないので，条件を満たしません．

入力例 2

2 3
XYX
YYY

出力例 2

0

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

入力例 3

2 58
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY

出力例 3

164036797

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

Score : 600 points

Problem Statement

There is a grid with H rows and W columns where each square has one of the characters X and Y written on it. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. The characters on the grid are given as H strings S_1, S_2, \dots, S_H: the j-th character of S_i is the character on square (i, j).

You can set up fences across the grid between adjacent rows and columns. Fences may intersect. After setting up fences, a block is defined as the set of squares reachable from some square by repeatedly moving up, down, left, or right to the adjacent square without crossing fences. (See also Sample Output 1.)

There are 2^{H-1} \times 2^{W-1} ways to set up fences. How many of them satisfy the following condition, modulo 998244353?

Condition: Each block has exactly two squares with Y written on it.

Constraints

  • 1 \leq H \leq 2000
  • 1 \leq W \leq 2000
  • S_i \ (1 \leq i \leq H) is a string of length W consisting of X and Y.

Input

The input is given from Standard Input in the following format:

H W
S_1
S_2
\vdots
S_H

Output

Print the number of ways to set up fences to satisfy the condition, modulo 998244353.

Sample Input 1

2 3
XYY
YXY

Sample Output 1

2

Below are the eight ways to set up fences.

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

For instance, if a fence is set up between the 2-nd and 3-rd columns, the blocks are:

XY
YX

Y
Y

Each of these blocks has exactly two Ys, so the condition is satisfied.

If a fence is set up between the 1-st and 2-nd rows and the 1-st and 2-nd columns, the blocks are:

X

YY

Y

XY

These blocks, except the second, do not have exactly two Ys, so the condition is not satisfied.

Sample Input 2

2 3
XYX
YYY

Sample Output 2

0

There is no way to set up fences to satisfy the condition.

Sample Input 3

2 58
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY

Sample Output 3

164036797

Print the number of ways modulo 998244353.