P6275 [USACO20OPEN] Sprinklers 2: Return of the Alfalfa P

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.

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 the number of ways to install sprinklers, modulo $10^9+7$.

#### 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.) ```plain 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