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