Red Rectangles

There is an $N \times M$ grid. Every cell is painted red or blue. The cell in row $i$ and column $j$ ($1 \le i \le N$, $1 \le j \le M$) is written as $(i, j)$.

Write a program that counts the rectangles made only of red cells. A rectangle is fixed by four integers $x_1, y_1, x_2, y_2$ with $1 \le x_1 \le x_2 \le N$ and $1 \le y_1 \le y_2 \le M$, and it holds every cell $(x, y)$ with $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$. For example, if $x_1 = 2$, $y_1 = 3$, $x_2 = 4$, $y_2 = 4$, the six cells $(2, 3)$, $(2, 4)$, $(3, 3)$, $(3, 4)$, $(4, 3)$, $(4, 4)$ all belong to one rectangle. Two rectangles are different when at least one of the four integers $x_1, y_1, x_2, y_2$ differs.

The first line contains the number of rows $N$ ($1 \le N \le 3000$) and the number of columns $M$ ($1 \le M \le 3000$), separated by a space.

Each of the next $N$ lines contains $M$ characters. Line $i$ gives the colors painted on row $i$ of the grid, and the $j$-th character of that line is the color of $(i, j)$. Every character is 'R' or 'B'. 'R' means the cell is red, and 'B' means it is blue.

Print the number of rectangles made only of red cells on the first line.

In the first example the 5 rectangles that satisfy the condition are listed below, written as $[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]$