F. Паша и труба
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

На очередном заседании правящей партии «A» министр Павел предложил усовершенствовать систему водопровода и проложить в городе новую трубу.

Город на карте представляет собой прямоугольное клетчатое поле размера n × m. Каждая клетка поля либо свободна (тогда труба может проходить по ней), либо занята (по такой клетке труба проходить не может). На карте свободные клетки обозначены символом '.', а занятые — '#'.

Труба должна удовлетворят следующим свойствам:

  • труба имеет вид ломанной ширины 1,
  • труба проходит по свободным клеткам,
  • труба начинается с края поля, но не с угловой клетки,
  • труба заканчивается на краю поля, но не в угловой клетке,
  • труба имеет не более 2-х поворотов (на 90 градусов),
  • на краях поля должно существовать ровно две клетки, по которым проходит труба,
  • если труба представляет собой один отрезок, то концевые точки трубы должны лежать на разных краях поля,
  • для каждой неконцевой клетки трубы существует ровно две соседние по стороне клетки, которые тоже принадлежат трубе,
  • для каждой из концевых клеток трубы существует ровно одна соседняя по стороне клетка, которая тоже принадлежит трубе.

Примеры разрешенных маршрутов для прокладывания труб:


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

Примеры запрещенных маршрутов для прокладывания труб:


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

В примерах трубы обозначены символами ' * '.

Вам поручили написать программу, которая вычисляет количество различных способов проложить ровно одну трубу на территории города.

Два способа прокладывания труб считаются различными, если они отличаются хотя бы в одной клетке.

Входные данные

В первой строке входных данных следуют два целых числа n, m (2 ≤ n, m ≤ 2000) — размеры карты Берляндии.

В следующих n строках задано по m символов — карта города.

Если клетка карты обозначена символом '.', значит она свободна, и по ней может проходить труба.

Если клетка карты обозначена символом '#', значит она занята, и труба по ней проходить не может.

Выходные данные

Выведите в первую строку выходных данных одно целое число — количество различных способов проложить ровно одну трубу.

Примеры
Входные данные
3 3
...
..#
...
Выходные данные
3
Входные данные
4 2
..
..
..
..
Выходные данные
2
Входные данные
4 5
#...#
#...#
###.#
###.#
Выходные данные
4
Примечание

В первом примере существует 3 способа проложить трубу (клетки трубы обозначены символами ' * '):


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