Задачи
Комнаты
Комнаты
Бизнесмен Петя недавно купил новый дом. В этом доме один этаж, разделённый на \textbf{n}×\textbf{m} одинаковых по размеру квадратных комнат, некоторые из которых будут жилыми, а в некоторых будут расположены кладовые.
Петя хочет, чтобы между некоторыми жилыми комнатами были проходы, и чтобы из любой жилой комнаты можно было добраться в любую другую жилую комнату, используя эти проходы, причём единственным образом. Проходы можно делать только между соседними комнатами, т.е. между теми, у которых есть общая стена.
Требуется посчитать количество различных способов соединить комнаты требуемым образом.
\InputFile
В первой строке входного файла содержатся числа \textbf{n} и \textbf{m} (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{12}). Далее следуют \textbf{n} строк по \textbf{m} символов в каждой, представляющие собой карту дома. Символ "\textbf{.}" соответствует жилой комнате, а "\textbf{*}" соответствует кладовой.
\OutputFile
Выведите одно число --- остаток от деления искомого количества на \textbf{10^9}.
Входные данные #1
2 2 .. ..
Выходные данные #1
4