[USACO OPEN 2021 P]Balanced Subsets
题号：NC222394
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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) for each 1≤i≤N, 1≤j≤N (1≤N≤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 (x1,y) and (x2,y) (x1≤x2) are part of the subset, then all cells (x,y) with x1≤x≤x2 are also part of the subset.
  4. If cells (x,y1)and (x,y2 (y1≤y2) are part of the subset, then all cells (x,y)with y1≤y≤y2 are also part of the subset.

Count the number of balanced subsets modulo 109+7.

输入描述:

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

输出描述:

The number of balanced subsets modulo 109+7.
示例1

输入

复制 
2
GG
GG

输出

复制 
13

说明


For this test case, 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

说明


Here is an example of a subset that satisfies the second condition (it is 4-connected) but does not satisfy the third condition:



GG..
.G..
GG..
....

备注:

Test cases 1-4 satisfy N≤4
Test cases 5-10 satisfy N≤20
Test cases 11-20 satisfy no additional constraints.
Problem credits: Benjamin Qi