Problem Background

Everyone is afraid of something. Some are afraid of the dark, some of heights, and some of Vinnie Jones...

Problem Description

Mirko's greatest fear is finding suitable land to grow strawberries. His land can be represented by an $N \times M$ matrix. Some plots are suitable for growing strawberries, while others are not, due to the overgrowth of weeds.

Mirko is looking for a suitable rectangle. A rectangle is considered suitable if it contains only plots suitable for growing strawberries.

Mirko is also interested in the potential value of each plot. The potential value of a plot is defined as the number of suitable rectangles that include this plot.

Calculate the sum of the potential values of all plots on Mirko's land.

Input Format

The first line contains two positive integers $N$ and $M$, representing the dimensions of the land.

The next $N$ lines each contain $M$ characters. A . indicates a plot suitable for growing strawberries, while a # indicates an unsuitable plot.

Output Format

Output the sum of the potential values of all plots on Mirko's land.

Sample Input and Output

Sample Input #1

2 3
.#.
..#

Sample Output #1

8

Sample Input #2

3 3
...
...
...

Sample Output #2

100

Sample Input #3

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

Sample Output #3

40

Notes

Sample 1 Explanation

The following matrix represents the potential values of each plot. The total sum of potential values is $8$.

Data Size and Constraints

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

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

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

Note

This problem's score is set according to the original COCI contest, with a maximum score of $110$.

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

见题面 Input 部分

见题面 Output 部分