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

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

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

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

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

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


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

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


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

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

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

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

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

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

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

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

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

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

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

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

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


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