Создание подземелий
Король демон ожидает в своем подземелье, чтобы сразиться с храбрым человеком. Подземелье представляет собой сетку размером H×W. Каждая ячейка соединена с четырьмя соседними ячейками (север, юг, восток и запад), и некоторые из них заняты препятствиями.
Чтобы атаковать храброго человека, король демон создал слугу, который блуждает по подземелью. Однако вскоре он обнаружил, что слуга не действует так, как задумано. Слуга слишком глуп: если в подземелье есть циклический путь, он может бесконечно ходить по этому циклу.
Чтобы гарантировать, что слуга в конечном итоге найдет храброго человека, король демон решил устранить все циклы, возводя стены между ячейками. При этом он должен быть осторожен, чтобы между любыми двумя ячейками, не занятыми препятствиями, существовал хотя бы один путь.
Ваша задача — написать программу, которая определит количество способов, которыми король демон может построить стены.
Входные данные
Первая строка каждого тестового случая содержит два целых числа H и W (1 ≤ H ≤ 500, 1 ≤ W ≤ 15), которые обозначают высоту и ширину подземелья. Следующие H строк содержат ровно W символов, каждый из которых — либо '.' (ячейка без препятствия), либо '#' (ячейка с препятствием). Гарантируется, что есть хотя бы одна ячейка без препятствия.
Ввод завершается, когда H=0 и W=0. В этом случае ваша программа не должна выводить результат.
Выходные данные
Для каждого тестового случая выведите номер случая и количество способов построить стены в одной строке. Поскольку ответ может быть очень большим, выведите его по модулю 1000000007.