시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 12 6 6 54.545%

문제

상근이는 N행 N열로 이루어진 모눈종이를 구매했다. 모눈종이는 가장 처음에 모든 칸이 흰 색이다. 상근이는 이 칸 중 일부를 검정색으로 칠하려고 한다.

모눈종이의 경계선을 따라서 붙어있는 칸을 선택한다면, 직사각형을 만들 수 있다. 그리고 그 직사각형 내부의 색이 모두 검정색이고, 크기가 두 칸 이상이라면, 이 직사각형을 검정 직사각형이라고 한다.

왼쪽에서 선택한 직사각형은 모두 검정 직사각형이 아니다. 1번 직사각형은 내부의 색 중 한 칸이 흰색이고, 2번은 한 칸이기 때문에 검정 직사각형이 아니다. 오른쪽 그림에서 선택한 세 개 직사각형은 모두 검정 직사각형이다.

이렇게 상근이가 적절히 색칠한 모눈종이가 주어졌을 때, 겹치는 칸이 없게 검정 직사각형 두 개를 선택하는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 1000) 다음 줄부터 N개 줄에는 각 모눈종이 칸의 색이 주어진다. C는 검정색, B는 흰색을 의미한다.

출력

첫째 줄에 겹치는 칸이 없게 두 검정 직사각형을 선택하는 방법의 수를 10007로 나눈 나머지 값을 출력한다.

예제 입력

5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB

예제 출력

8

힌트