P1950 Rectangle

Xiao Ming had a sudden idea today: he wants to cut out a rectangle from a used sheet of paper. To simplify the problem, Xiao Ming makes the following rules: (1) The paper’s length and width are $n,m$. Xiao Ming views this sheet as consisting of $n\times m$ cells, and when cutting, he can only cut along the edges of the cells. (2) There are some places on this paper that Xiao Ming drew on before; the cut-out rectangle cannot contain any previously drawn places. (3) There is no restriction on the size of the rectangle. Xiao Ming looks at this sheet and comes up with many ways to cut it, but how many ways are there exactly? He cannot count them all. Can you help him?

The first line contains two positive integers $n,m$, representing the length and width of the sheet. Then there are $n$ lines, each with $m$ characters. Each character is either `*` or `.`. The character `*` means this cell was drawn on before, and the character `.` means this cell was not drawn on before.

Output a single integer, the number of ways.

Constraints For $10\%$ of the testdata, $1\leq n\leq 10,1\leq m\leq 10$. For $30\%$ of the testdata, $1\leq n\leq 50,1\leq m\leq 50$. For $100\%$ of the testdata, $1\leq n\leq 1000,1\leq m\leq 1000$. Translated by ChatGPT 5