Black Rectangles

Time limit1sMemory limit128 MB

Summary

Count unordered pairs of disjoint all-black axis-aligned rectangles (each containing at least two cells) in an up to 1000x1000 grid, modulo 10007.

Level: Hard8 of 10
Topics: Prefix sum, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

You are given an N by N grid paper. Initially every cell is white, and some cells have been colored black.

You may choose one rectangular region whose sides follow the grid lines. If every cell inside the chosen rectangle is black and the rectangle contains at least two cells, it is called a black rectangle.

The three rectangles on the left are not black rectangles. Rectangle 1 contains one white cell, and rectangle 2 contains only one cell. The three rectangles selected on the right are all black rectangles.

Given the colored grid, count the number of ways to choose two black rectangles so that they do not share any cell.

Input

The first line contains an integer N. (2 <= N <= 1000)

Each of the next N lines gives the colors of one row of the grid. C means black, and B means white.

Output

Print the number of ways to choose two black rectangles with no shared cell, modulo 10007.

Examples3

Example 1
Input
```
2
CC
CC
```
Expected output
```
2
```
Example 2
Input
```
3
CCB
CCB
CBB
```
Expected output
```
5
```
Example 3
Input
```
5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB
```
Expected output
```
8
```