尽管 Mirko 已经体验了所有最有趣的游乐设施，但他的热情依然没有消退。他打开了他的方格纸笔记本，开始给方格涂色，这时一个全新的、更难的问题浮现在他的脑海中。

给你一个由 $N$ 行 $N$ 列组成的方格表。每个格子要么是黑色，要么是白色。

如果一个由格子组成的矩形（其水平和垂直边与格子边界重合）满足其内部的所有格子都是黑色，且它包含至少两个格子，则称其为黑色矩形。

左图展示了两个不属于黑色矩形的矩形。标记为 1 的矩形不是黑色矩形，因为它包含一个白色格子；标记为 2 的矩形不是黑色矩形，因为它只包含一个格子。另一方面，右图展示了三个合法的黑色矩形。

计算选择两个没有公共格子的黑色矩形的可能方案数。由于答案可能非常大，你应该输出该方案数模 $10\,007$ 的余数。

输入格式

输入的第一行包含整数 $N$ ($2 \le N \le 1000$)。

接下来的 $N$ 行，每行包含方格表的一行，由 $N$ 个字符组成。字符 'C' 代表黑色格子，而 'B' 代表白色格子。

输出格式

输出的第一行也是唯一的一行，必须包含所需方案数除以 $10\,007$ 的余数。

样例

输入样例 1

2
CC
CC

输出样例 1

2

输入样例 2

3
CCB
CCB
CBB

输出样例 2

5

输入样例 3

5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB

输出样例 3

8