Компания «Замки и замки» недавно разработала новый тип кодового замка, для размещения на воротах замков. Панель замка представляет собой прямоугольник шириной w ячеек и высотой h ячеек. В некоторых из них расположены кнопки.
Код на этом замке вводится одновременным нажатием нескольких кнопок (их не может быть меньше трех). Для того, чтобы код было легче запомнить, используемые в нем кнопки должны образовывать связную область. Область называется связной, если из любой клетки области можно добраться до любой другой, перемещаясь только между клетками этой области с общей стороной. Важным критерием надежности замка является число различных кодов, которые на нем можно набрать. Новым кодом может считаться только код, включающий такую группу кнопок, которая никак не связана с другой группой
Для оценки надежности замков требуется написать программу для вычисления количества различных кодов замка.
Выходные данные
В первой строке находятся два целых числа h, w (1 ≤ h, w ≤ 30). Каждая из последующих h строк содержит w символов. Символ «#» обозначает кнопку, а «.» — ее отсутствие.
Выходные данные
Выведите единственное число — количество кодов, удовлетворяющих указанным требованиям.
| № | Входные данные | Выходные данные |
|
1
|
2 2
.#
##
|
1
|
|
2
|
5 6
.#....
##.##.
..#.#.
.####.
.....#
|
2
|