题目描述

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，即苜蓿）

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