#873 WhiteBlue

問題文

問題文の言語

$N \times M$ のマス目の各マスを白または青で塗る。一部のマスはすでに塗られており、その色を変更することはできない。

残りのマスをすべて塗る。ただし、横に連続する3マス、または 縦に連続する3マス がすべて同じ色になってはならない。

この条件を満たす塗り方の総数を求めよ。

入力は次の形式で与えられる。

$N\ M$ $S_1$ $S_2$

条件を満たす塗り方の総数を $1\,000\,000\,007$ で割った余りを出力せよ。

#	得点	制約
1	15	$N \le 2$ , $M \le 6$ .
2	20	$N \le 4$ , .

例 1

入力例

1 3
...

出力例

6

$2^3=8$ 通りのうち、3マスがすべて白またはすべて青である2通りを除く。

例 2

入力例

3 1
W
.
W

出力例

1

中央のマスは青で塗る必要がある。

例 3

入力例

2 3
W..
.B.

出力例

9

例 4

入力例

3 3
WWW
...
...

出力例

0