P7532 [USACO21OPEN] Balanced Subsets P

题目描述

Farmer John 的草地可以被看作是由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘），对于每一个 $1≤i≤N$、$1≤j≤N$，方格可以用有序对 $(i,j)$ 表示。某些方格中含有草。

方格的一个非空子集被称为是「平衡的」，如果以下条件成立：

• 1. 所有子集中的方格均含有草。
• 2. 子集是四连通的。换句话说，从子集中的任一方格到另一方格均存在一条路径使得路径中的相邻方格均水平或竖直方向上相邻。
• 3. 如果方格 $(x_1,y)$ 和 $(x_2,y)$（$x_1≤x_2$）存在于子集中，那么所有满足 $x_1≤x≤x_2$ 的方格 $(x,y)$ 也存在于子集中。
• 4. 如果方格 $(x,y_1)$ 和 $(x,y_2)$（$y_1≤y_2$）存在于子集中，那么所有满足 $y_1≤y≤y_2$ 的方格 $(x,y)$ 也存在于子集中。

计算平衡的子集数量模 $10^9+7$ 的结果。

输入格式

输入的第一行包含 $N$。

以下 $N$ 行每行包含一个长为 $N$ 的字符串。如果方格 $(i,j)$ 中有草，则第 $i$ 行的第 $j$ 个字符为 $\texttt{G}$，否则为$\texttt{.}$。

输出格式

输出平衡的子集数量模 $10^9+7$ 的结果。

输入输出样例 1

2
GG
GG

13

输入输出样例 2

4
GGGG
GGGG
GG.G
GGGG

642

说明/提示

样例一解释

对于这个测试用例，所有的四连通子集均是平衡的。

G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG

样例二解释

以下是一个符合第二个条件（四连通）但不符合第三个条件的子集的例子：

GG..
.G..
GG..
....

数据范围与约定

$1\le N \le 150$ 。