В лаборатории биоинформатики ученые проводят эксперименты по распространению искусственно созданных вирусов. Для эксперимента используется специальная лабораторная установка, представляющая собой таблицу из \(n \times m\) ячеек. В каждую ячейку помещается живая клетка. Ученые заражают вирусом некоторые клетки, всего исходно заражается не более 8 клеток.
Каждую секунду среди незараженных клеток, имеющих зараженную клетку в соседней по стороне ячейке, ровно одна клетка заражается вирусом.
Ученые заинтересовались, какие конфигурации зараженных клеток могут получиться через \(t\) секунд. Для начала они хотят посчитать число таких конфигураций. Помогите им это сделать.
В первой строке входного файла находятся целые числа \(n\), \(m\) и \(t\) (\(1 \le n, m \le 100\), \(1 \le t \le 6\)) - размеры таблицы и количество секунд.
Каждая из следующих \(n\) строк содержит \(m\) символов. Символ <<.>> означает, что в изначальной конфигурации клетка не заражена, а символ <<*>> - что заражена. Количество <<*>> в таблице не превышает 8.
Гарантируется, что незараженных клеток в исходной конфигурации не меньше \(t\).
Выведите количество различных возможных конфигураций таблицы после \(t\) секунд.
2 2 1 *. ..
2
2 2 2 *. ..
3
2 2 3 *. ..
1