P5230 [AHOI2013] The Very Square Snake

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. .jpg) Now the snake wants you to help compute how many pairs of disjoint subsnakes there are. Output the answer modulo 10007.

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 one integer, the answer.

$1~\leq~N~\leq~1000$ Translated by ChatGPT 5