Farmer John 有一块小田地，形状为 $N$ 行 $N$ 列的网格（$1 \le N \le 2000$）。对于所有 $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)$。

被一个或多个甜玉米喷灌器灌溉的格子可以种植甜玉米；被一个或多个苜蓿喷灌器灌溉的格子可以种植苜蓿。但是，被两种喷灌器都灌溉的格子（或两种喷灌器都未灌溉的格子）什么也不能种植。

请帮助 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

说明

这满足下文所述的第一个子任务的限制。

子任务

• 测试点 3–4 满足 $N\le 10$，并且未被占据的格子至多有十个。
• 测试点 5–9 满足 $N\le 200$。
• 测试点 10–16 没有额外限制。

题目作者：Benjamin Qi