Masala H

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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