CS:GO

题目描述

Rifleman is a student who majors in Computer Science , and he is playing GO now.

Consider an $n\times m$ chessboard where each cell can be in one of three states: a black piece, a white piece, or empty. Consider a maximal four-connected component consisting only of pieces of the same color. If there is no empty cell among the cells directly adjacent to this connected component, the configuration is considered invalid(This rule is quite similar to Go).

We call a component $S$ maximal if there is no component $T$ such that $S$ is a proper subset of $T$.

Now, given an incomplete chessboard, you need to fill each ? with one of the three states so that the resulting configuration is valid. Count the number of ways to do this. Since the number may be large, output it modulo $998244353$.

输入格式

The first line contains two integers $n(1\leq n\leq 20)$ and $m(1\leq m\leq 7)$, the dimensions of the chessboard.

The next $n$ lines each contain $m$ characters, describing the chessboard. The characters mean:

B: a black piece

W: a white piece

.: an empty cell

?: a cell you need to fill

输出格式

Print a integer — the answer modulo $998244353$.

样例输入 #1

2 2
B?
?W

样例输出 #1

5

样例输入 #2

3 3
?W.
W?W
???

样例输出 #2

108