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