Душевая кабина
Степан приобрел душевую кабину и решил установить её в своём дачном доме. Дом имеет форму прямоугольника размером NхМ, разделённого на единичные квадраты. Степан знает, что душевая кабина занимает ровно две соседние клетки, которые имеют общую сторону. Также ему известно, что некоторые клетки дома уже заняты различными предметами.
Помогите Степану определить, сколькими различными способами он может разместить душевую кабину в дачном доме.
Формат входных данных:
В первой строке находятся два целых числа N, М (1 ≤ N, М ≤ 1000) — размеры дачного дома Степана. Каждый из следующих N строк содержит по М символов, описывающих план дома. Символ "#" обозначает, что соответствующая клетка занята, а символ "." — что она свободна и может быть использована для установки душевой кабины.
Формат выходных данных:
Выведите одно число — количество способов разместить душевую кабину в дачном доме.