3395. [USACO20 Open Platinum]Return of the Alfalfa

题目长度过长过不了审，稍微缩减了一下，原题目为： Sprinklers 2: Return of the Alfalfa

【题目描述】

Farmer John 有一块小的田地，形状为一个 $N$ 行 $N$ 列的一个方阵（$1 \le N \le 2000$），对于所有的 $1 \le i,j \le N$，从上往下的第 $i$ 行的从左往右第 $j$ 个方格记为 $(i,j)$。他有兴趣在他的田地里种植甜玉米和苜蓿。为此，他需要安装一些特殊的洒水器。

在方格 $(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$。

对于每一个 $1\le i\le N$，第 $i+1$ 行包含一个长为 $N$ 的字符串，表示方阵的第 $i$ 行。字符串中的每个字符为 'W'（表示被一头长毛奶牛占据的方格）或 '.'（未被占据）。

【输出格式】

输出安装洒水器的方法数除以 $10^9+7$ 的余数。

【样例输入1】

2
..
..

【样例输出1】

28

【样例输入2】

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

【样例输出2】

2304

【样例解释】

样例 1 解释:

以下是所有十四种可以使得 $(1,1)$ 生长甜玉米的方式。(译注：C 表示 sweet corn，即甜玉米；A 表示 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.  ..  ..

样例 2 解释:

这个样例符合第一个子任务的限制。

【提示】

对于$ 25\% $的测试数据(测试点$ 1 \sim 4 $)，满足$ N \le 10 $，且至多只有十个未被占据的方格。

对于$ 56\% $的测试数据(测试点$ 1 \sim 9 $)，满足$ N \le 200 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 美国公开赛 Platinum 组