Strah

Time limit1sMemory limit256 MB

Summary

For an N by M grid of '.' and '#', find the sum over all '.' cells of the number of all-'.' subrectangles containing it.

Level: Medium7 of 10
Topics: Stack, Combinatorics, Implementation, Math
Solved: No attempts yet

Problem

Everyone is afraid of something. Someone is afraid of darkness, someone is afraid of heights, someone is afraid of Vinnie Jones (all of us are afraid of Vinnie Jones), someone is afraid of singing before eating something...

There are many fears, but the greatest among all for Mirko is choosing a land for planting strawberries. Mirko's land can be described as a matrix with N rows and M columns. Some of the fields in the matrix are suitable for planting strawberries and some are not; weeds grow there. Mirko is looking for rectangular parts of the land that are completely filled with fields suitable for strawberry planting. Those kind of rectangles are called suitable rectangles. Also, Mirko is interested in the potential value of all fields in the matrix. The potential value of each field in the matrix is defined as the number of suitable rectangles that contain that field.

Since Mirko has troubles facing his fears, he asks you to only calculate the sum of all the fields' potential values.

Input

The first line contains two positive integers N and M (1 ≤ N, M ≤ 2 000), dimensions of the land. The next N lines contains M characters each, representing the landscape. Each character can be either a ‘.’ (dot) which represents a field suitable for planting or a ‘#’ which represents weeds.

Output

Output the sum of all potential values of the matrix's fields.

Examples3

Example 1
Input
```
2 3
.#.
..#
```
Expected output
```
8
```
Example 2
Input
```
3 3
...
...
...
```
Expected output
```
100
```
Example 3
Input
```
3 4
..#.
#...
...#
```
Expected output
```
40
```