Problem Description

One day, the cute snake was so happy that she turned herself into a square. But while transforming, she was induced, which caused some problems.

As planned, she should have become a completely black $N*N$ square, but some white cells appeared in this square. Now her body unfortunately had some small reactions: define a subsnake as an all-black rectangle with at least two cells.

Now the snake wants you to help compute how many pairs of disjoint subsnakes there are. Output the answer modulo 10007.

Input Format

The first line contains an integer $N$. Then follow $N$ lines, each a string of length $N$. If a character is $B$, the cell is black; if it is $W$, the cell is white.

Output Format

Output one integer, the answer.

3 
BBW
BBW 
BWW 

5

Hint

$1~\leq~N~\leq~1000$

Translated by ChatGPT 5