P7306 [COCI 2018/2019 #1] Strah

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

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.

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 the sum of the potential values of all cells in Mirko's land.

#### Sample 1 Explanation The following matrix represents the potential value of each cell. The sum of the potential values of all cells is $8$. |$2$|$0$|$1$| | :----------: | :----------: | :----------: | |$3$|$2$|$0$| #### 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](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #1](https://hsin.hr/coci/archive/2018_2019/contest1_tasks.pdf) _T4 Strah_.** Translated by ChatGPT 5