레이팅 미적용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 ".".
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.
The first line of input contains \(n\) and \(m\) (\(1 \le n\), \(m \le 500\)), the dimensions of the wall.
In each of the next \(n\) lines, there are \(m\) characters \(c_{ij}\), describing the wall. Each character will be either
"." or "#" (without quotes).
In a single line of output, print the number of possible ways to place the picture on the wall.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 17점 | n, \(m \le 10\) |
2 | 21점 | n, \(m \le 100\) |
3 | 32점 | No additional constraints. |
3 3
...
...
..#364 4
....
.#..
#...
#.#.765 5
.....
#..#.
..#.#
.....
..#..154Clarification 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.