Control Towers

시간 제한2초메모리 제한2048 MB

요약

빈 칸 네 곳에 네 개의 관제탑을 놓되 이웃한 관제탑끼리 같은 행이나 같은 열에 오도록 하는 배치의 수를 센다.

난이도: 보통10점 중 7점
유형: 조합론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

You are an architect tasked with designing the new airport in your city. After you have completed your design, you just realize you forgot to allocate spaces for the control towers.

The layout of the new airport can be represented by a 2D grid of $r$ rows and $c$ columns, with the rows numbered from $1$ to $r$ (top to bottom) and the columns numbered from $1$ to $c$ (left to right). The cell in row $i$ and column $j$ is denoted by $(i, j)$ . Each cell can either be occupied or empty.

You need to place four control towers (numbered from $1$ to $4$ ), each in a different empty cell. To allow easier communication between different towers, for all $k = 1, 2, 3$ , you want tower $k$ and tower $k + 1$ to be placed either in the same row or in the same column.

You want to calculate the number of ways to place the control towers to satisfy the requirements above. Two ways are considered different if there exists $k$ where control tower $k$ is placed in different cells.

입력

The first line of input contains two integers $r$ and $c$ ( $1 ≤ r, c ≤ 2000$ ). Each of the next $r$ lines contains a string of $c$ characters. The $j$ -th character in the $i$ -th line is # if cell $(i, j)$ is occupied; otherwise, it is . (dot).

출력

Output the number of ways to place the control towers to satisfy the requirements above.

예제4

예제 1
입력
```
3 4
.#.#
#...
.###
```
예상 출력
```
10
```
예제 2
입력
```
4 6
######
#.#.#.
.#.#.#
######
```
예상 출력
```
0
```
예제 3
입력
```
1 10
..........
```
예상 출력
```
5040
```
예제 4
입력
```
1 10
##########
```
예상 출력
```
0
```