Migrated from Lutece 2790 驱逐摆摆人 2

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大大超人是卷王。 大大超人讨厌摆烂的废物。 大大超人决定驱逐那些摆烂的摆摆人。

大大超人所在的地方可以看做一个 $N\times N$ 的正方形区域，每个位置 $(i,j)(1\le i,j\le N)$ 上都有一个摆摆人。 大大超人决定用两种方法驱逐摆摆人。 一是在 $(X,Y)$ 位置督促他们训练，这样会使得所有 $(X\le i\le N,1\le j\le Y)$ 的 $(i,j)$ 位置的摆摆人去训练而不是摆烂。 二是在 $(X,Y)$ 位置督促他们卷文化课，这样会使得所有 $(1\le i\le X,Y\le j\le N)$ 的 $(i,j)$ 位置的摆摆人去卷文化课而不是摆烂。

但摆摆人是很摆的，所以如果一个位置的摆摆人又被督促去训练又被督促去卷文化课，他就会因为太累而彻底躺平，而这是大大超人所厌恶的，所以他不想让这种情况发生。

由于大大超人不屑于在摆摆人身上花费太多时间，所以在每个位置最多督促摆摆人一次。 由于某些懒得编的原因，大大超人不会去某些位置督促摆摆人。

大大超人想知道他有多少种驱逐摆摆人的方案，使得每个位置摆摆人都去训练或卷文化课，不同方案当且仅当在某个位置上的操作不同（督促训练/督促卷文化课/什么也不做）。

大大超人当然知道问题的答案，但是为了不让你摆掉，他将问题丢给了你。 由于答案可能很大，输出其对 $10^9+7$ 取模的结果。

Input

第一行一个正整数 $N$。 接下来 $N$ 行每行一个长度为 $N$ 的字符串表示第 $i$ 行的情况。如果第 $j$ 个字符为 $W$ 则表示大大超人不会到 $(i,j)$ 督促摆摆人，字符只可能为 $.$ 或 $W$。

Output

输出可能的方案数对 $10^9+7$ 取模后的结果

Samples

2
..
..

28

3
.W.
W.W
.W.

40

7
.WWWW..
W.WWWWW
W.WW.W.
WWWWWWW
WWW.WWW
WWWWWWW
WW.WWW.

1088

Constraints

$1\le N\le 2000$

Resources

2022 UESTC ICPC Training for Dynamic Programming