P7532 [USACO21OPEN] Balanced Subsets P

Farmer John's pasture can be viewed as a huge two-dimensional square grid made of square cells (imagine a huge chessboard). For each $1 \le i \le N$ and $1 \le j \le N$, a cell can be represented by the ordered pair $(i,j)$. Some cells contain grass. A non-empty subset of cells is called "balanced" if the following conditions hold: 1. All cells in the subset contain grass. 2. The subset is 4-connected. In other words, from any cell in the subset to any other cell in the subset, there exists a path such that every pair of adjacent cells on the path are adjacent horizontally or vertically. 3. If cells $(x_1,y)$ and $(x_2,y)$ ($x_1 \le x_2$) are in the subset, then all cells $(x,y)$ with $x_1 \le x \le x_2$ are also in the subset. 4. If cells $(x,y_1)$ and $(x,y_2)$ ($y_1 \le y_2$) are in the subset, then all cells $(x,y)$ with $y_1 \le y \le y_2$ are also in the subset. Compute the number of balanced subsets modulo $10^9+7$.

The first line contains $N$. The next $N$ lines each contain a string of length $N$. If cell $(i,j)$ contains grass, then the $j$-th character of the $i$-th line is $\texttt{G}$; otherwise it is $\texttt{.}$.

Output the number of balanced subsets modulo $10^9+7$.

#### Explanation for Sample 1 For this test case, every 4-connected subset is balanced. ``` G. .G .. .. GG .G .. G. GG .G G. GG GG .., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG ``` #### Explanation for Sample 2 Below is an example of a subset that satisfies the second condition (4-connected) but does not satisfy the third condition: ``` GG.. .G.. GG.. .... ``` #### Constraints $1 \le N \le 150$. Translated by ChatGPT 5