시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

В лаборатории биоинформатики ученые проводят эксперименты по распространению искусственно созданных вирусов. Для эксперимента используется специальная лабораторная установка, представляющая собой таблицу из $n \times m$ ячеек. В каждую ячейку помещается живая клетка. Ученые заражают вирусом некоторые клетки, всего исходно заражается не более 8 клеток. 

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

Ученые заинтересовались, какие конфигурации зараженных клеток могут получиться через $t$ секунд. Для начала они хотят посчитать число таких конфигураций. Помогите им это сделать.

입력

В первой строке входного файла находятся целые числа $n$, $m$ и $t$ ($1 \le n, m \le 100$, $1 \le t \le 6$) --- размеры таблицы и количество секунд.

Каждая из следющих $n$ строк содержит $m$ символов. Символ <<.>> означает, что в изначальной конфигурации клетка не заражена, а символ <<*>> --- что заражена. Количество <<*>> в таблице не превышает 8.

Гарантируется, что незараженных клеток в исходной конфигурации не меньше $t$.

출력

Выведите количество различных возможных конфигураций таблицы после $t$ секунд.

예제 입력 1

2 2 1
*.
..

예제 출력 1

2

예제 입력 2

2 2 2
*.
..

예제 출력 2

3

예제 입력 3

2 2 3
*.
..

예제 출력 3

1