|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||10||6||6||60.000%|
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\le i\le N$, $1\le j\le N$ ($1\le N\le 150$). Some of the cells contain grass.
A nonempty subset of grid cells is called "balanced" if the following conditions hold:
Count the number of balanced subsets modulo $10^9+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 $10^9+7$.
2 GG GG
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
4 GGGG GGGG GG.G GGGG
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.. ....