Bifurcated Irrigation

Farmer John has an N×N square field (with rows and columns both numbered 1 through N). In each cell (i,j) he may install at most one sprinkler, unless the cell is occupied by a cow (in which case a sprinkler cannot be installed though the cell may still be watered). There are two types of sprinklers:

• A sweet corn sprinkler placed in cell ((I,J)) waters all cells in the bottom‐left region, i.e. all cells ((i,j)) satisfying (I \le i) and (j \le J).
• An alfalfa sprinkler placed in cell ((I,J)) waters all cells in the top‐right region, i.e. all cells ((i,j)) satisfying (i \le I) and (J \le j).

For each cell in the field, let the water it receives be defined as follows:

• If it is watered by one or more sweet corn sprinklers (and no alfalfa sprinkler), then it can grow sweet corn.
• If it is watered by one or more alfalfa sprinklers (and no corn sprinkler), then it can grow alfalfa.
• If it is watered by both types or by none, nothing grows in that cell.

John wishes to install sprinklers (choosing for each empty cell either no sprinkler, or a sprinkler of one of the two types) so that every cell in the field receives exactly one type of watering (and thus can grow a crop). Compute the number of valid installation schemes modulo \(10^9+7\).

Important note: A cell that currently has a cow is not allowed to have a sprinkler installed, but can still be watered by sprinklers placed in other cells.

inputFormat

The first line contains a single integer (N) (the size of the field). The next (N) lines each contain a string of length (N). In the grid, a character '.' denotes an empty cell where a sprinkler can be placed, and a character '*' denotes a cell occupied by a cow (sprinkler cannot be installed in these cells).

outputFormat

Output a single integer: the number of valid sprinkler installation schemes modulo (10^9+7).

sample

2
..
..

1