「USACO 2020 US Open Platinum」Sprinklers 2: Return of the Alfalfa - Problem

Farmer John 有一块大小为 $N \times N$ 的网格形土地，将从上到下第 $i$ 行、从左到右第 $j$ 列（$1 \le i, j \le N$）的格子记作 $(i, j)$。

他想要在这片土地上种植甜玉米和紫苜蓿（mù xu），所以他需要安装一些特别的洒水器。

一个安装在 $(I, J)$ 的甜玉米洒水器会为所有在左下角方向的格子（也就是所有满足 $I \le i$，$j \le J$ 的格子 $(i, j)$）洒水。

一个安装在 $(I, J)$ 的紫苜蓿洒水器会为所有在右上角方向的格子（也就是所有满足 $i \le I$，$J \le j$ 的格子 $(i, j)$）洒水。

如果一个格子被一个或多个甜玉米洒水器喷洒到，那么它就能够种植甜玉米；如果一个格子被一个或多个紫苜蓿洒水器喷洒到，那么它就能够种植紫苜蓿。但是如果一个格子被两种洒水器都喷洒到了（或都没喷洒到），那么它就什么都种不了。

请你帮助 FJ 计算安装洒水器的方案数（对 ${10}^9 + 7$ 取模），满足每个格子最多安装一个洒水器，且每个格子都能种植（也就是说，每个格子恰好被一种洒水器喷洒到）。

有些格子已经被毛乎乎的奶牛占据了，导致这些格子上不能放置洒水器，但不影响格子能否种植植物。

从标准输入中读入数据。

第一行一个正整数 $N$。
接下来 $N$ 行，第 $i$ 行一个长度为 $N$ 的字符串，表示网格第 $i$ 行的状态。字符串中只包含 W 和 . 两种字符，如果第 $j$ 个字符为 W 则表示 $(i, j)$ 被毛乎乎的奶牛占据了，否则表示没有被占据。

输出到标准输出中。

输出安装洒水器的方案数，对 ${10}^9 + 7$ 取模。

input

2
..
..

output

下列是甜玉米能种植在 $(1, 1)$ 的 $14$ 种情况。

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

input

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

output

此样例满足第一个子任务（见下）的限制。

对于所有数据，$1 \le N \le 2000$。

对于测试点 $3 \sim 4$，满足 $N \le 10$ 且最多有 $10$ 个未被占据的格子。
对于测试点 $5 \sim 9$，满足 $N \le 200$。
对于测试点 $10 \sim 16$，无特殊限制。

出题人：Benjamin Qi

HelloWorld信息学奥赛题库