Problem Description

Farmer John has a small field shaped like an $N$ by $N$ grid. For all $1 \le i,j \le N$, the cell in the $i$-th row from top to bottom and the $j$-th column from left to right is denoted $(i,j)$. He is interested in planting sweet corn and alfalfa in his field. To do so, he needs to install some special sprinklers.
A sweet corn sprinkler in cell $(I,J)$ can water all cells to its lower-left, i.e., all $(i,j)$ such that $I \le i$ and $j \le J$.

An alfalfa sprinkler in cell $(I,J)$ can water all cells to its upper-right, i.e., all $(i,j)$ such that $i \le I$ and $J \le j$.

A cell watered by one or more sweet corn sprinklers can grow sweet corn; a cell watered by one or more alfalfa sprinklers can grow alfalfa. However, a cell watered by both types of sprinklers (or by neither type) cannot grow anything.

Help Farmer John compute the number of ways to install sprinklers in his field ( $\bmod \ 10^9 + 7$). At most one sprinkler may be installed in each cell, and every cell must be able to grow a crop (i.e., be watered by exactly one type of sprinkler).

Some cells are occupied by hairy cows; this does not prevent those cells from growing crops, but sprinklers cannot be installed in those cells.

Input Format

The first line contains an integer $N$.
For each $1\le i\le N$, the $(i+1)$-th line contains a string of length $N$, describing the $i$-th row of the grid. Each character is either W (a cell occupied by a hairy cow) or . (unoccupied).

Output Format

Output the number of ways to install sprinklers, modulo $10^9+7$.

2
..
..

28

4
..W.
..WW
WW..
...W

2304

Hint

Explanation for Sample $1$:

Below are all $14$ ways that make $(1,1)$ grow sweet corn. (Translator's note: C means sweet corn; A means alfalfa.)

CC  .C  CA  CC  .C  CA  CA  C.  CA  C.  CC  .C  CC  .C
CC, CC, CC, .C, .C, .C, CA, CA, .A, .A, C., C., .., ..

Notes for Sample $2$:

This sample satisfies the constraints of the first subtask.

For $100\%$ of the testdata, $1 \le N \le 2000$.

There are $16$ test points. Points $1 \sim 2$ are the samples, and the rest have the following properties:

For test points $3 \sim 4$, $N \le 10$ and there are at most $10$ unoccupied cells.
For test points $5 \sim 9$, $N \le 200$.
For test points $10 \sim 16$, there are no special constraints.

Problem author: Benjamin Qi

Translated by ChatGPT 5