U158665 [USACO21OPEN] Balanced Subsets P

题目来源：USACO 2021 Open Platinum Problem 3

Farmer John 的草地可以被看作是由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘），对于每一个 $1≤i≤N$、$1≤j≤N$，方格可以用有序对 $(i,j)$ 表示（$1≤N≤150$）。某些方格中含有草。 方格的一个非空子集被称为是「平衡的」，如果以下条件成立： 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$ 个字符为 $G$，否则为$.$。

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

样例1： 对于这个测试用例，所有的四连通子集均是平衡的。 ```plain G. .G .. .. GG .G .. G. GG .G G. GG GG .., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG ``` 样例2： 以下是一个符合第二个条件（四连通）但不符合第三个条件的子集的例子： ```plain GG.. .G.. GG.. .... ``` 测试点性质： - 测试点 1-4 满足 $N≤4$。 - 测试点 5-10 满足 $N≤20$。 - 测试点 11-20 没有额外限制。