Description

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$.

Input Format

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 Format

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

2
GG
GG

13

4
GGGG
GGGG
GG.G
GGGG

642

Hint

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