Description

Although Mirko has found all the most interesting rides, his enthusiasm still has not faded. He opens a notebook with squared paper and starts coloring the squares. A new and even harder problem comes to his mind.

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

If all cells of some rectangular shape inside the grid are black, and the rectangle consists of at least two cells, then this rectangle is called a black rectangle.

The top-left picture shows two examples that are not black rectangles. Rectangle $1$ is not a black rectangle because it contains one white cell; rectangle $2$ is not a black rectangle because it contains only one cell. The top-right picture shows three examples of black rectangles.

Compute the number of ways to choose two black rectangles that do not share any cells. Since the answer may be very large, you should output the remainder of this number modulo $10^4 + 7$.

Input Format

The first line contains an integer $n$, whose meaning is described above.

The next $n$ lines each contain an uppercase string of length $n$, consisting only of C (meaning the cell is black) and B (meaning the cell is white), describing the grid.

Output Format

Print one integer: the number of ways to choose two black rectangles with no common cells, modulo $10^4 + 7$.

2
CC
CC

2

3
CCB
CCB
CBB

5

5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB

8

Hint

Constraints

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

Notes

• This problem is worth $130$ points in total.
• Translated from COCI2010-2011 CONTEST #2 CRNI, translator
  https://www.luogu.com.cn/user/115711

Translated by ChatGPT 5