[USACO20OPEN] Sprinklers 2: Return of the Alfalfa P
题目描述
Farmer John 有一块小的田地,形状为一个 $N$ 行 $N$ 列的一个方阵,对于所有的 $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)$。
被一个或多个甜玉米洒水器喷洒到的方格可以长出甜玉米;被一个或多个苜蓿洒水器喷洒到的方格可以长出苜蓿。但是被两种洒水器均喷洒到(或均喷洒不到)的方格什么也长不出来。
帮助 Farmer John 求出在他的田地里安装洒水器的方案数( $\bmod \ 10^9 + 7$),每个方格至多安装一个洒水器,使得每个方格均能生长作物(即被恰好一种洒水器喷洒到)。
某些方格正被长毛奶牛占据;这不会阻止这些方格生长作物,但是这些方格里不能安装洒水器。
输入输出格式
输入格式
输入的第一行包含一个整数 $N$。
对于每一个 $1\le i\le N$,第 $i+1$ 行包含一个长为 $N$ 的字符串,表示方阵的第 $i$ 行。字符串中的每个字符为 `W`(表示被一头长毛奶牛占据的方格)或 `.`(未被占据)。
输出格式
输出安装洒水器的方案数 $\bmod \ 10^9+7$ 的结果。
输入输出样例
输入样例 #1
2
..
..
输出样例 #1
28
输入样例 #2
4
..W.
..WW
WW..
...W
输出样例 #2
2304
说明
#### 样例 $1$ 解释:
以下是所有十四种可以使得 $(1,1)$ 生长甜玉米的方式。(译注:`C` 表示 sweet corn,即甜玉米;`A` 表示 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., .., ..
```
#### 样例 $2$ 提示:
这个样例满足第一个子任务的限制。
-----
对于 $100\%$ 的数据,满足 $1 \le N \le 2000$。
共 $16$ 个测试点,其中 $1\sim 2$ 为样例,其余性质如下:
对于测试点 $3 \sim 4$,满足 $N \le 10$ 且最多有 $10$ 个未被占据的格子。
对于测试点 $5 \sim 9$,满足 $N \le 200$。
对于测试点 $10 \sim 16$,无特殊限制。
---
出题人:Benjamin Qi