Description

Mirko is most afraid of finding suitable land to grow strawberries. His land can be represented as an $N \times M$ matrix. Some cells are suitable for growing strawberries, and some are not, because they are overgrown with weeds.

Mirko is looking for a suitable rectangle. If a rectangular region in the land contains only cells that are suitable for growing strawberries, then this rectangle is called a suitable rectangle.

Mirko is also interested in the potential value of every cell. The potential value of a cell is defined as the number of suitable rectangles that contain this cell.

Find the sum of the potential values of all cells in Mirko's land.

Input Format

The first line contains positive integers $N, M$, representing the size of the land.

The next $N$ lines each contain $M$ characters. . means the cell is suitable for growing strawberries, and # means it is not suitable.

Output Format

Output the sum of the potential values of all cells in Mirko's land.

2 3
.#.
..#

8

3 3
...
...
...

100

3 4
..#.
#...
...#

40

Hint

Sample 1 Explanation

The following matrix represents the potential value of each cell. The sum of the potential values of all cells is $8$.

Constraints

For $20\%$ of the testdata, $1 \le N, M \le 10$.

For another $30\%$ of the testdata, $1 \le N, M \le 300$.

For $100\%$ of the testdata, $1 \le N, M \le 2000$.

Notes

The scoring of this problem follows the original COCI problem settings, with a full score of $110$.

This problem is translated from COCI2018-2019 CONTEST #1 T4 Strah.

Translated by ChatGPT 5