This page is still under construction.

Parts of this page are still being built. What you see may change.

Balanced Subsets

Time limit1sMemory limit512 MB

Summary
Count connected subsets of grass cells in an N by N grid where every row and column intersects the subset in a single contiguous run, modulo 1e9+7.
Level

Hard8 of 10

Topics
Dynamic programming, Implementation, Matrix, Combinatorics
Solved
No attempts yet

Problem

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≤i≤N1\le i\le N, 1≤j≤N1\le j\le N (1≤N≤1501\le N\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 (x1,y)(x_1,y) and (x2,y)(x_2,y) (x1≤x2x_1\le x_2) are part of the subset, then all cells (x,y)(x,y) with x1≤x≤x2x_1\le x\le x_2 are also part of the subset.
  4. If cells (x,y1)(x,y_1) and (x,y2)(x,y_2) (y1≤y2y_1\le y_2) are part of the subset, then all cells (x,y)(x,y) with y1≤y≤y2y_1\le y\le y_2 are also part of the subset.

Count the number of balanced subsets modulo 109+710^9+7.

Input

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.

Output

Print the number of balanced subsets modulo 109+710^9+7.

Examples2

  1. Example 1

    Input
    2
    GG
    GG
    
    Expected output
    13
    
  2. Example 2

    Input
    4
    GGGG
    GGGG
    GG.G
    GGGG
    
    Expected output
    642