#P1950. Rectangle Cutting

    ID: 15232 Type: Default 1000ms 256MiB

Rectangle Cutting

Rectangle Cutting

Little Ming had an idea today: he wanted to cut out a rectangle from a used sheet of paper. The paper is of size $n \times m$ and is divided into $n \times m$ grid cells. Some cells already contain drawings (marked cells). When cutting, Ming can only cut along the grid lines, and the resulting rectangle must not contain any previously drawn (marked) cells. The rectangle can be of any size as long as it lies along the grid lines.

Determine the number of ways to cut out a rectangle (by choosing a subrectangle of the grid) that does not contain any pre-drawn cell.

inputFormat

The first line contains two integers $n$ and $m$, representing the number of rows and columns of the paper.

Each of the following $n$ lines contains a string of $m$ characters. Each character is either . representing a free cell or * representing a cell with a previous drawing. You can assume $1 \le n, m \leq$ (a reasonable upper limit).

outputFormat

Output a single integer: the number of ways to cut out a rectangle that does not include any pre-drawn cell.

sample

1 1
.
1