Balanced Subsets

문제

Farmer John's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chessboard) labeled by the ordered pairs $(i,j)(i,j)$ for each $1\le i\le N1\backslash le\; i\backslash le\; N$, $1\le j\le N1\backslash le\; j\backslash le\; N$ ($1\le N\le 1501\backslash le\; N\backslash le\; 150$). Some of the cells contain grass.

A nonempty subset of grid 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, there exists a path from any cell in the subset to any other cell in the subset such that every two consecutive cells of the path are horizontally or vertically adjacent.
3. If cells $(x_1,y)(x\_1,y)$ and $(x_2,y)(x\_2,y)$ ($x_1\le x_{2}x\_1\backslash le\; x\_2$) are part of the subset, then all cells $(x,y)(x,y)$ with $x_1\le x\le x_{2}x\_1\backslash le\; x\backslash le\; x\_2$ are also part of the subset.
4. If cells $(x,y_1)(x,y\_1)$ and $(x,y_2)(x,y\_2)$ ($y_1\le y_{2}y\_1\backslash le\; y\_2$) are part of the subset, then all cells $(x,y)(x,y)$ with $y_1\le y\le y_{2}y\_1\backslash le\; y\backslash le\; y\_2$ are also part of the subset.

Count the number of balanced subsets modulo ${10}^9+710^9+7$.

입력

The first line contains $NN$.

The next $NN$ lines each contain a string of $NN$ characters. The $jj$-th character of the $ii$-th line from the top is equal to G if the cell at $(i,j)(i,j)$ contains grass, or . otherwise.

출력

The number of balanced subsets modulo ${10}^9+710^9+7$.

2
GG
GG

13

4
GGGG
GGGG
GG.G
GGGG

642