Комнаты
Комнаты
Бизнесмен Петя недавно купил новый дом. В этом доме один этаж, разделённый на n×m одинаковых по размеру квадратных комнат, некоторые из которых будут жилыми, а в некоторых будут расположены кладовые.
Петя хочет, чтобы между некоторыми жилыми комнатами были проходы, и чтобы из любой жилой комнаты можно было добраться в любую другую жилую комнату, используя эти проходы, причём единственным образом. Проходы можно делать только между соседними комнатами, т.е. между теми, у которых есть общая стена.
Требуется посчитать количество различных способов соединить комнаты требуемым образом.
Input data
В первой строке входного файла содержатся числа n и m (1 ≤ n, m ≤ 12). Далее следуют n строк по m символов в каждой, представляющие собой карту дома. Символ "." соответствует жилой комнате, а "*" соответствует кладовой.
Output data
Выведите одно число — остаток от деления искомого количества на 10^9.
Examples
2 2 .. ..
4