Problem Description

Despite finding all the most interesting attractions, Mirko's enthusiasm remains undiminished. He opens his grid paper notebook and starts coloring squares, when a new and even more challenging problem comes to his mind.

You are given an $n \times n$ grid. Each cell is either black or white.

A rectangle within the grid is called a black rectangle if all its cells are black and it consists of at least two cells.

The left image above shows two examples that are not black rectangles. The rectangle marked as $1$ is not a black rectangle because it contains a white cell; the rectangle marked as $2$ is not a black rectangle because it consists of only one cell. The right image shows three examples of black rectangles.

Calculate the number of ways to select two black rectangles that do not share any common cells. Since the result may be very large, you should output the number modulo $10^4 + 7$.

Input Format

The first line contains an integer $n$, as described in the problem statement.

The next $n$ lines each contain a string of length $n$ consisting of uppercase characters C (indicating a black cell) and B (indicating a white cell), representing the grid.

Output Format

A single line containing an integer, which is the number of ways to select two black rectangles modulo $10^4 + 7$.

Sample Input and Output

Sample Input #1

2
CC
CC

Sample Output #1

2

Sample Input #2

3
CCB
CCB
CBB

Sample Output #2

5

Sample Input #3

5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB

Sample Output #3

8

Notes

Data Constraints

For $100\%$ of the data, it is guaranteed that $2 \leq n \leq 1 \times 10^3$, and each character in the input strings is either C or B. Let $|s|$ be the length of each string, then $|s| = n$.

Additional Notes

• This problem is worth $130$ points.
• The problem is translated from COCI2010-2011 CONTEST #2 CRNI, translated by @mnesia.

见题面 Input 部分

见题面 Output 部分