문제
검은 칸과 하얀 칸으로 이뤄진 N행 N열의 격자가 있다.
검은 사각형이란 격자의 칸들을 사각형의 형태로 선택했을 때, 포함되는 칸들의 색이 모두 검은색이고, 선택한 칸의 수가 2개 이상인 것을 말한다.
위의 왼쪽 그림에서 1번의 경우에는 선택한 칸의 색이 모두 검은색이 아니기 때문에 검은 사각형이 아니다. 2번의 경우에는 선택한 칸의 색은 모두 검은색이지만 선택한 칸의 개수가 1개이기 때문에 검은 사각형이 아니다.
격자가 주어졌을 때, 선택한 칸이 서로 겹치지 않게 한번에 2개의 검은 사각형을 만들 수 있는 모든 경우의 수를 출력하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 격자의 크기 N ( 2≤N≤1,000)이 입력된다. 그 다음 줄부터 N행 N열로 격자의 형태가 입력되며 'C'의 경우 검은 칸을 뜻하고, 'B'의 경우 하얀칸을 뜻한다.
출력
입력에 대해 가능한 경우의 수를 10,007로 나눈 나머지를 출력하라.
예제1
입력
2
CC
CC
출력
2
예제2
입력
3
CCB
CCB
CBB
출력
5
예제3
입력
5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB
출력
8
출처
COCI 2010/2011 Contest #2 6번