C2CRNI - Crni

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.

The left image shows two rectangles which are not black rectangles. The rectangle labelled 1 is not a black rectangle because it contains a white cell, and the rectangle labelled 2 is not a black rectangle because it consists of only one cell. On the other hand, the right image shows three valid black rectangles.

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.

Input

The first line of input contains the integer N (2 ≤ N ≤ 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.

Output

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

Example

Input:
2
CC
CC

Output:
2

Input:

3
CCB
CCB
CBB

Output:
5

Input:

5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB

Output:
8

Added by:Race with time
Date:2010-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:COCI 2010-2011 2-nd Round

hide comments
2013-01-18 11:29:32 Ehor Nechiporenko
Hey, Time is not too strict. I have created O(n*n) solution, and it took the first place even without code optimizations, and after small optimizing i made my code work even faster.

Last edit: 2013-01-18 11:52:58
2010-11-23 12:45:16 stjepan
I'm the author of the problem and I agree. :)
2010-11-21 17:12:32 gustav
yup, my code passes under 0.5 seconds on the actual contest judge, yet on SPOJ it takes more than ten times longer...

Last edit: 2010-11-21 17:12:52
2010-11-19 09:19:26 Ivan Katanic
time limit too strict
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.