[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$ 的结果。

2
..
..

28

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

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