빨간 직사각형 Batch Compilation commands

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

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

입력

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

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

출력

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

부분문제

부분문제	점수	N, M
1	10	≤ 500
2	10	≤ 3,000

입출력 예제

입력

2 2
RR
RB

출력

5

5개의 직사각형은 다음과 같다. ($[x_{1}$, $y_{1}$, $x_{2}$, $y_{2}]$으로 나타냄)

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