COCI 2010/2011 Contest #2 6번- 검은 사각형 > 문제은행 : 정보올림피아드&알고리즘




2367 : 검은 사각형

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
12 회   
시도횟수
37 회   

문제

검은 칸과 하얀 칸으로 이뤄진 N행 N열의 격자가 있다.


검은 사각형이란 격자의 칸들을 사각형의 형태로 선택했을 때, 포함되는 칸들의 색이 모두 검은색이고, 선택한 칸의 수가 2개 이상인 것을 말한다.


 


 


 


 


위의 왼쪽 그림에서 1번의 경우에는 선택한 칸의 색이 모두 검은색이 아니기 때문에 검은 사각형이 아니다. 2번의 경우에는 선택한 칸의 색은 모두 검은색이지만 선택한 칸의 개수가 1개이기 때문에 검은 사각형이 아니다.


격자가 주어졌을 때, 선택한 칸이 서로 겹치지 않게 한번에 2개의 검은 사각형을 만들 수 있는 모든 경우의 수를 출력하는 프로그램을 작성하라.


입력형식

입력의 첫 줄에는 격자의 크기 N ( 2≤N≤1,000)이 입력된다.
그 다음 줄부터 N행 N열로 격자의 형태가 입력되며 'C'의 경우 검은 칸을 뜻하고, 'B'의 경우 하얀칸을 뜻한다.


출력형식

입력에 대해 가능한 경우의 수를 10,007로 나눈 나머지를 출력하라.


입력 예

2
CC
CC

출력 예

2

입력 예

3
CCB
CCB
CBB

출력 예

5

입력 예

5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB

출력 예

8


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP