C2CRNI - Crni

尽管Mirko找到了所有最有趣的游乐设施，但他的热情仍然没有消失，于是他无聊地打开了方格笔记本，开始给方块涂色，于是一个新的甚至更难的问题浮现了出来。 现在有个$N\times N$的矩阵，每个格子被填充了黑色或者白色。如果这个矩形的一个子矩形内的所有格子均为黑色并且由至少两个格子组成，则这个子矩形称为**黑矩形**。  左图框选了两个不是黑矩形的子矩形。1号子矩形不是黑矩形，因为它包含了白色的格子；2号子矩形不是黑矩形，因为它仅包含一个格子。右图框选了三个有效的黑矩形。 现在Mirko想知道找出两个不相交的黑矩形的方案的总数目。由于结果可能非常大，因此你的答案需要对$10007$取模。 ### 输入格式 第一行为一个整数$N$ 接下来$N$行每行$N$个字母表示矩阵每个格子的颜色。`C`为黑色，`B`为白色。 ### 输出格式 不相交黑矩形对的数量对$10007$取模后的值。 ### 样例 #### 样例#1 输入： ``` 2 CC CC ``` 输出： ``` 2 ``` #### 样例#2 输入： ``` 3 CCB CCB CBB ``` 输出： ``` 5 ``` #### 样例#3 输入： ``` 5 BCCBB BBCBB BCCBB BBBBB CCBBB ``` 输出： ``` 8 ```

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. (IMAGE) 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.

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

\n2 \nCC \nCC\n\n

\n2\n\nInput:\n3 \nCCB \nCCB \nCBB\n\nOutput:\n5\n\nInput:\n5\nBCCBB\nBBCBB\nBCCBB\nBBBBB\nCCBBB\n\nOutput:\n8