Кімнати#3697
Бізнесмен Петя нещодавно придбав новий будинок. У цьому будинку є один поверх, розділений на n \times m однакових квадратних кімнат. Деякі з цих кімнат будуть житловими, а інші — коморами.
Петя хоче, щоб між певними житловими кімнатами були проходи, і щоб з будь-якої житлової кімнати можна було дістатися до будь-якої іншої житлової кімнати, використовуючи ці проходи, причому лише одним способом. Проходи можна робити тільки між сусідніми кімнатами, тобто тими, що мають спільну стіну.
Необхідно підрахувати кількість різних способів з'єднати кімнати таким чином.
У першому рядку вхідного файлу містяться числа і (1 \leq n, m \leq 12). Далі йдуть рядків по символів у кожному, що представляють карту будинку. Символ "." позначає житлову кімнату, а "*" — комору.
Виведіть одне число — остачу від ділення шуканої кількості на 10^9.
Приклад 1