Even though he has found all the most amusing rides, Mirko's enthusiasm still isn't fading. He opened his graph paper notebook and started colouring squares, and a new, even harder problem dawned on him.

You are given a square table consisting of \(N\) rows by \(N\) columns. Each cell is either black or white.

A set of cells forming a rectangle, with horizontal and vertical edges following cell borders, shall be called a black rectangle if all cells inside the rectangle are black and it consists of at least two cells.

Calculate the number of possible selections of two black rectangles that have no common cells. As the required number can be extremely large, you should output the remainder of dividing that number by \(10\,007\).

The first line of input contains the integer \(N\) (\(2 \le N \le 1000\)).

Each of the next \(N\) lines contains a single row of the table, consisting of \(N\) symbols. The symbol C represents a black cell, while B represents a white cell.

The first and only line of output must contain the remainder of dividing the required number by \(10\,007\).

riseoj 작성

출처 COCI 2010/2011 Contest 2