#3283. 「USACO 2020 US Open Platinum」Sprinklers 2: Return of the Alfalfa

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: PinkRabbit

题目描述

题目译自 USACO 2020 US Open Contest, Platinum Problem 1. Sprinklers 2: Return of the Alfalfa

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 取模。

样例

样例输入 1

2
..
..

样例输出 1

28

样例解释 1

下列是甜玉米能种植在 (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., .., ..

样例输入 2

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

样例输出 2

2304

样例解释 2

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

数据范围与提示

对于所有数据, 1 \le N \le 2000

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

出题人:Benjamin Qi