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:
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.