[Usaco2020 Open]Sprinklers 2-Return of the Alfalfa

内存限制：512 MiB 时间限制：10 Sec

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

在方格 (I,J) 中的甜玉米洒水器可以喷洒到所有左下方的方格：即满足 I≤i 以及 j≤J 的 (i,j)。

在方格 (I,J) 中的苜蓿洒水器可以喷洒到所有右上方的方格：即满足 i≤I 以及 J≤j 的 (i,j)。

被一个或多个甜玉米洒水器喷洒到的方格可以长出甜玉米；被一个或多个苜蓿洒水器喷洒到的方格可以长出苜蓿。但是被两种洒水器均喷洒到（或均喷洒不到）的方格什么也长不出来。

帮助 FJ 求出在他的田地里安装洒水器的方法数（模 10^9+7），每个方格至多安装一个洒水器，使得每个方格均能生长作物（即被恰好一种洒水器喷洒到）。

某些方格正被长毛奶牛占据；这不会阻止这些方格生长作物，但是这些方格里不能安装洒水器。

输入的第一行包含一个整数 N。

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

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

样例输入


			2

..

..

样例输出


			28

以下是所有十四种可以使得 (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., .., ..

#5567. [Usaco2020 Open]Sprinklers 2-Return of the Alfalfa

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示