Farmer John has a small field in the shape of an \(N\) by \(N\) grid
(\(1 \le N \le 2000\)) where the \(j\)-th square from the left of the \(i\)-th row
from the top is denoted by \((i,j)\) for all \(1 \le i,j \le N\). 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 square \((I,J)\) will sprinkle all squares to the
bottom-left: i.e. \((i,j)\) with \(I \le i\) and \(j \le J\).

An alfalfa sprinkler in square \((I,J)\) will sprinkle all squares to the
top-right: i.e. \((i,j)\) with \(i \le I\) and \(J \le j\).

A square sprinkled by one or multiple sweet corn sprinklers can grow sweet corn;
a square sprinkled by one or multiple alfalfa sprinklers can grow alfalfa. But a
square sprinkled by both types of sprinklers (or neither type) can grow nothing.

Help FJ determine the number of ways (modulo \(10^9 + 7\)) to install sprinklers
in his field, at most one per square, so that every square is fertile (i.e.,
sprinkled by exactly one type of sprinkler).

Some of the squares are already occupied by woolly cows; this doesn't prevent
these squares from being fertile, but no sprinklers can be installed in such
squares.

Problem credits: Benjamin Qi

SCORING

• Test cases 3-4 satisfy \(N\le 10\) and there are at most ten unoccupied squares.
• Test cases 5-9 satisfy \(N\le 200\).
• Test cases 10-16 satisfy no additional constraints.

Problem credits: Benjamin Qi

The first line contains a single integer \(N.\)

For each \(1\le i\le N,\) the \(i+1\)-st line contains a string of length \(N\)
denoting the \(i\)-th row of the grid. Each character of the string is one of 'W'
(indicating a square occupied by a woolly cow), or '.' (unoccupied).

Output the remainder when the number of ways to install sprinklers is divided by
\(10^9+7.\)

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Platinum