빨간 직사각형 Batch 컴파일 명령

N × M 크기의 격자판이 있다. 격자판의 각 칸은 빨간색 또는 파란색으로 색칠되어 있다. 편의상 i행 j열 (1 ≤ i ≤ N, 1 ≤ j ≤ M)의 격자를 (i, j)로 표시한다.

주어진 격자판 내에서 빨간색 격자로만 이루어진 직사각형의 개수를 세는 프로그램을 작성하자. 여기서 직사각형은 1 ≤ x₁ ≤ x₂ ≤ N, 1 ≤ y₁ ≤ y₂ ≤ M를 만족하는 네 개의 정수 x₁, y₁, x₂, y₂에 의해 결정되며, x₁ ≤ x ≤ x₂와 y₁ ≤ y ≤ y₂를 만족하는 모든 격자 (x, y)를 일컫는다. 예를 들어 x₁ = 2, y₁ = 3, x₂ = 4, y₂ = 4라면, 6개의 격자 (2, 3), (2, 4), (3, 3), (3, 4), (4, 3), (4, 4)가 모두 한 직사각형에 속한다. 두 직사각형이 서로 다르다는 것은 [x₁, y₁, x₂, y₂]이 서로 다르다는 것이다.

입력

첫 번째 줄에 행의 수 N (1 ≤ N ≤ 3,000)과 열의 수 M (1 ≤ M ≤ 3,000)이 공백을 사이로 두고 주어진다.

다음 N개의 줄의 각 줄에는 M개의 문자가 주어진다. 이 중 i (1 ≤ i ≤ N)번째 줄은 주어진 격자판의 i번째 행의 격자에 칠해진 색들을 나타내며, 이 중 j번째 문자는 (i, j)에 칠해진 색을 나타낸다. 모든 문자는 'R' 또는 'B'로만 구성된다. 'R'은 해당 칸이 빨간색임을, 'B'는 해당 칸이 파란색임을 의미한다.

출력

첫 번째 줄에 빨간색 격자로만 이루어진 직사각형의 개수를 출력한다.

부분문제

입출력 예제

5개의 직사각형은 다음과 같다. ([x₁, y₁, x₂, y₂]으로 나타냄)

• [1, 1, 1, 1]
• [1, 1, 1, 2]
• [1, 2, 1, 2]
• [1, 1, 2, 1]
• [2, 1, 2, 1]