Вирус

시간 제한2초메모리 제한512 MB

요약

최대 8개의 감염된 세포에서 시작해 매초 감염된 세포에 인접한 미감염 세포 하나가 감염될 때, t초 후 도달 가능한 서로 다른 격자 상태의 수를 센다.

난이도: 보통10점 중 6점
유형: BFS, 시뮬레이션, 조합론
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

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

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

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

출력

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

예제3

예제 1
입력
```
2 2 1
*.
..
```
예상 출력
```
2
```
예제 2
입력
```
2 2 2
*.
..
```
예상 출력
```
3
```
예제 3
입력
```
2 2 3
*.
..
```
예상 출력
```
1
```