CF518F.Pasha and Pipe

On a certain meeting of a ruling party "A" minister Pavel suggested to improve the sewer system and to create a new pipe in the city.

The city is an n × m rectangular squared field. Each square of the field is either empty (then the pipe can go in it), or occupied (the pipe cannot go in such square). Empty squares are denoted by character '.', occupied squares are denoted by character '#'.

The pipe must meet the following criteria:

• the pipe is a polyline of width 1,
• the pipe goes in empty squares,
• the pipe starts from the edge of the field, but not from a corner square,
• the pipe ends at the edge of the field but not in a corner square,
• the pipe has at most 2 turns (90 degrees),
• the border squares of the field must share exactly two squares with the pipe,
• if the pipe looks like a single segment, then the end points of the pipe must lie on distinct edges of the field,
• for each non-border square of the pipe there are exacly two side-adjacent squares that also belong to the pipe,
• for each border square of the pipe there is exactly one side-adjacent cell that also belongs to the pipe.

Here are some samples of allowed piping routes:

....# ....# .*..#
***** ****. .***.
..#.. ..#*. ..#*.
#...# #..*# #..*#
..... ...*. ...*.

Here are some samples of forbidden piping routes:

.**.# *...# .*.*#
..... ****. .*.*.
..#.. ..#*. .*#*.
#...# #..*# #*.*#
..... ...*. .***.

In these samples the pipes are represented by characters ' * '.

You were asked to write a program that calculates the number of distinct ways to make exactly one pipe in the city.

The two ways to make a pipe are considered distinct if they are distinct in at least one square.

在执政党“A”某次会议上，帕维尔部长提议改进城市排水系统，并在城市中新建一条管道。

该城市是一个 $n \times m$ 的矩形网格区域。网格中的每个方格要么为空（管道可穿过），要么被占据（管道不可穿过）。空方格用字符 . 表示，被占据的方格用字符 # 表示。

管道必须满足以下条件：

• 管道是一条宽度为 1 的折线；
• 管道仅穿过空方格；
• 管道起点位于网格边界上，但不能是角上的方格；
• 管道终点也位于网格边界上，但不能是角上的方格；
• 管道至多有 2 个拐弯（每次拐弯为 90 度）；
• 管道与网格边界方格恰好相交于两个方格；
• 若管道呈单一（无拐弯的）线段，则其两个端点必须位于网格的不同边界边上；
• 对于管道中每一个非边界方格，恰好有两个与其边相邻（即上下左右）的方格也属于该管道；
• 对于管道中每一个边界方格，恰好有一个与其边相邻的方格也属于该管道。

以下是若干允许的管道路径示例：

....# ....# .*..#
***** ****. .***.
..#.. ..#*. ..#*.
#...# #..*# #..*#
..... ...*. ...*.

以下是若干禁止的管道路径示例：

.**.# *...# .*.*#
..... ****. .*.*.
..#.. ..#*. .*#*.
#...# #..*# #*.*#
..... ...*. .***.

在上述示例中，管道由字符 * 表示。

你需要编写一个程序，计算在该城市中恰好铺设一条管道的不同方案总数。

若两种方案在至少一个方格上不同，则认为它们是不同的方案。

The first line of the input contains two integers n, m (2 ≤ n, m ≤ 2000) — the height and width of Berland map.

Each of the next n lines contains m characters — the map of the city.

If the square of the map is marked by character '.', then the square is empty and the pipe can through it.

If the square of the map is marked by character '#', then the square is full and the pipe can't through it.

输入的第一行包含两个整数 $n$、$m$（$2 \leq n, m \leq 2000$）—— 分别表示 Berland 地图的高度和宽度。

接下来的 $n$ 行，每行包含 $m$ 个字符，表示该城市的地图。

若地图上的某个方格标记为字符 .，则该方格为空，管道可以穿过它。

若地图上的某个方格标记为字符 #，则该方格被占据，管道无法穿过它。

In the first line of the output print a single integer — the number of distinct ways to create a pipe.

在输出的第一行打印一个整数——构建管道的不同方式的数量。

In the first sample there are 3 ways to make a pipe (the squares of the pipe are marked by characters ' * '):

.*. .*. ...
.*# **# **#
.*. ... .*.

在第一个样例中，共有 3 种方式可以构成一根管道（管道所占的方格用字符 * 标出）：

.*. .*. ...
.*# **# **#
.*. ... .*.