Задача 38134. Balanced Subsets

Farmer John's pasture can be represented as a huge 2D grid of cells labeled with ordered pairs (i,j) for all 1≤i≤N, 1≤j≤N (1≤N≤150). Some of these slots contain grass.
A non-empty subset of lattice cells is called "balanced" if the following conditions are met:

All subset cells contain grass.
The subset is 4-connected. In other words, there is a path from any cell in the subset to any other cell in the subset such that two consecutive cells of the path are horizontally or vertically adjacent.
If cells (x₁,y) (x₂,y) (x₁≤x₂) is part of the subset, then all cells (x,y) with x₁≤x≤x₂ are also part of the subset.
If cells (x,y₁) and (x,y₂) (y₁≤y₂ ) is part of the subset, then all cells (x,y) with y₁≤y≤y₂ are also part of the subset.
Count the number of balanced subsets modulo 10⁹+7.

Input: 
The first line contains the number N.
Each of the subsequent N lines contains a string of N characters. The j-th character of string i from the top is equal to G if cell (i,j) contains grass or character . otherwise.

Output: 
Number of balanced subsets modulo 10⁹+7.
 

Examples

#	Input	Output	Explanation
1	2 GG GG	13	For this test, all 4-connected subsets are balanced. G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG .., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG
2	4 GGGG GGGG GG.G GGGG		642 Below is an example of a subset that satisfies the second condition (4-connectedness) but does not satisfy the third condition: GG.. .G.. GG.. ....