zid — COCI CONTEST_#5
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 13
Algorithms: line sweep, prefix sum, combinatorics

# Task Zid

**Task Zid**

Mr. Malnar wants to put up a picture of himself on the wall. The wall can be represented as a matrix with *n* rows and *m* columns. Since he has placed his picture on the wall many times before, some positions still have nails embedded in them. Such positions are marked with the symbol \"#\", while empty spots are marked with the symbol \".\".

![Wall with nails and empty spots](./_page_0_Picture_4.jpeg)

The picture has a rectangular shape with arbitrary dimensions and is placed on the wall in a way that it covers a rectangular area. The picture can be placed on the wall if it covers at most one position that contains a nail.

Help Mr. Malnar calculate the number of ways he can place his picture on the wall.

### Input

The first line of input contains *n* and *m* (1 ≤ *n, m* ≤ 500), the dimensions of the wall.

In each of the next *n* lines, there are *m* characters *c<sub>ij</sub>*, describing the wall. Each character will be either \".\" or \"#\" (without quotes).

### Output

In a single line of output, print the number of possible ways to place the picture on the wall.

### Scoring

| Subtask | Points | Constraints               |
|---------|--------|---------------------------|
| 1       | 17     | n, m ≤ 10                |
| 2       | 21     | n, m ≤ 100               |
| 3       | 32     | No additional constraints |

### Examples

**Example 1:**

```
input
3 3
...
...
..#
output
36
```

**Example 2:**

```
input
4 4
....
.#..
#...
#.#.
output
76
```

**Example 3:**

```
input
5 5
.....
#..#.
..#.#
.....
..#..
output
154
```

### Clarification of the first example:

Each placement of the picture is valid as long as it covers at most one nail.

### Clarification of the second example:

The picture cannot be placed in a way that it covers positions (3, 1) and (4, 1) simultaneously.

Starter code: