Электросеть
После неожиданной кончины предыдущего арендатора, вы были назначены новым "главным архитектором" Звезды Смерти по распоряжению самого Лорда Вейдера. Ваша задача — спроектировать систему проводки для распределения энергии по каждому сектору Звезды Смерти. Осознавая, что ваша жизнь зависит от успешного выполнения этой задачи, вы решили тщательно и всесторонне рассмотреть все возможные конфигурации проводки, чтобы выбрать наилучшую.
Вам предоставлена карта Звезды Смерти в виде сетки размером m×n, где каждая ячейка представляет собой сектор. Один из секторов на карте является электростанцией; остальные сектора либо жилые помещения, либо складские единицы. Вы можете установить соединение между любыми двумя не складскими секторами, которые находятся рядом по вертикали или горизонтали. Допустимая конфигурация проводки должна соответствовать следующим условиям:
Каждый сектор жилых помещений должен быть соединен с сектором электростанции, напрямую или через другие сектора.
Используется минимальное количество соединений (т.е. удаление любого соединения приведет к отключению какого-либо жилого помещения от электростанции).
Для данной карты, сколько существует допустимых конфигураций проводки?
Входные данные
Входные данные содержат несколько тестовых случаев. Каждый тестовый случай начинается с одной строки, содержащей два целых числа m и n (где 1 ≤ m ≤ 8 и 1 ≤ n ≤ 8). Далее следуют m строк, каждая из которых содержит n символов, представляющих карту Звезды Смерти. Карта содержит ровно один сектор, обозначенный как электростанция (P); остальные сектора либо жилые помещения (.), либо складские единицы (#). Гарантируется, что существует хотя бы одна допустимая конфигурация проводки. Конец ввода обозначается строкой "0 0", которую не следует обрабатывать.
Выходные данные
Для каждого тестового случая входных данных выведите количество допустимых конфигураций проводки mod 1000000000.
