검은 직사각형
시간 제한1초메모리 제한128 MB
최대 1000x1000 격자에서 모든 칸이 검은색이고 칸이 2개 이상인 두 사각형을 서로 겹치지 않게 고르는 방법의 수를 10007로 나눈 나머지로 구합니다.
문제
N행 N열 모눈종이가 있다. 처음에는 모든 칸이 흰색이며, 그중 일부 칸이 검은색으로 칠해져 있다.
모눈종이의 격자선에 맞추어 하나의 직사각형 영역을 고를 수 있다. 선택한 직사각형의 모든 칸이 검은색이고, 포함된 칸의 수가 두 칸 이상이면 그 직사각형을 검은 직사각형이라고 한다.
왼쪽 그림의 세 직사각형은 검은 직사각형이 아니다. 1번 직사각형에는 흰 칸이 하나 포함되어 있고, 2번 직사각형은 한 칸뿐이기 때문이다. 오른쪽 그림에서 선택한 세 직사각형은 모두 검은 직사각형이다.
검은색과 흰색으로 칠해진 모눈종이가 주어질 때, 서로 겹치는 칸이 없도록 검은 직사각형 두 개를 선택하는 방법의 수를 구하시오.
입력
첫째 줄에 정수 N이 주어진다. (2 <= N <= 1000)
다음 N개 줄에는 각 모눈종이 칸의 색이 주어진다. C는 검은색, B는 흰색을 의미한다.
출력
서로 겹치는 칸이 없도록 검은 직사각형 두 개를 선택하는 방법의 수를 10007로 나눈 나머지를 출력한다.