Two Convex Shapes

题目描述

有一只鸭嘴兽接到任务：把一个网格中的每个格子涂成黑色或白色，并且最终涂色需要满足下面两个条件。

条件 1：同色连通

对于每一种颜色，所有该颜色的格子必须连通。

形式化地说，若两个颜色为 $X$ 的格子之间存在一条只经过颜色为 $X$ 的格子的路径，并且路径中相邻两个格子有公共边，则称这两个格子连通。要求对每种颜色 $X\in{\texttt{B},\texttt{W}}$，任意两个颜色为 $X$ 的格子都必须连通。

条件 2：同色行列凸

对于每一种颜色，该颜色的格子集合必须在网格意义下是凸的。这里的“凸”不是普通几何意义上的凸，而是指：

• 在每一行中，该颜色出现的位置必须构成一个连续区间，可以为空，也可以是整行；
• 在每一列中，该颜色出现的位置也必须构成一个连续区间，可以为空，也可以是整列。

等价地说：如果同一行或同一列中有两个格子都是同一种颜色，那么它们之间的所有格子也必须是该颜色。

特别允许

整张网格可以被涂成全白或全黑。此时另一种颜色为空集，视为满足上述条件。

---

鸭嘴兽可能已经涂好了一些格子。给定一个字符网格 grid，其中第 $i$ 行第 $j$ 列的字符表示该格子的当前状态，行列均从 $0$ 开始编号。

字符含义如下：

• W：该格子已经被涂成白色；
• B：该格子已经被涂成黑色；
• ?：该格子尚未确定颜色。

现在需要把所有 ? 分别填成 B 或 W。设满足上述两个条件的填色方案数量为 $X$。请输出

[ X\bmod 1000000007. ]

两种涂色方案不同，当且仅当至少有一个格子的颜色不同。

输入格式

第一行包含一个整数 $H$，表示网格的行数。

接下来 $H$ 行，每行包含一个字符串，表示当前网格的一行。所有字符串长度相同，设其长度为 $W$。字符串仅由字符 B、W、? 组成。

输出格式

输出一个整数，表示满足条件的填色方案数对 $1000000007$ 取模后的结果。

数据范围

• $1\le H\le 50$；
• $1\le W\le 50$；
• 所有输入字符串长度均为 $W$；
• 每个字符均为 B、W、? 之一。

样例 1

输入

2
??
??

输出

14

样例 2

输入

2
B?
??

输出

7

样例 3

输入

2
B?
?B

输出

3

样例 4

输入

2
BW
??

输出

3

样例 5

输入

4
WWB
WWW
WWW
WWW

输出

1

样例 6

输入

3
BBBBBB
WWBBBB
WBBBBB

输出

0

样例 7

输入

3
?BB?
BBBB
?BB?

输出

5

样例 8

输入

3
???
???
???

输出

66

样例 9

输入

5
?????
?????
?????
?????
?????

输出

986

样例 10

输入

5
W???W
?????
?????
?????
W???W

输出

1