Farmer John 有一块 $N \times N$ 的网格状小农田（$1 \le N \le 2000$），其中从上往下第 $i$ 行、从左往右第 $j$ 列的方格记为 $(i,j)$，其中 $1 \le i,j \le N$。他想在农田里种植甜玉米和苜蓿。为此，他需要安装一些特殊的喷灌器。

位于 $(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$。

对于每个 $1 \le i \le N$，第 $i+1$ 行包含一个长度为 $N$ 的字符串，表示网格的第 $i$ 行。字符串中的每个字符要么是 'W'（表示被奶牛占据的方格），要么是 '.'（表示未被占据）。

输出安装喷灌器的方法数对 $10^9 + 7$ 取模后的结果。

样例

输入格式 1

2
..
..

输出格式 1

28

说明

这里列出了当 $(1,1)$ 可以种植甜玉米时的全部十四种可能性。

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

说明

这满足下述第一个子任务的约束条件。

SCORING

• 测试点 3-4 满足 $N \le 10$，且至多有十个未被占据的方格。
• 测试点 5-9 满足 $N \le 200$。
• 测试点 10-16 无额外约束。