Бизнесмен Петя недавно купил новый дом. В этом доме один этаж, разделённый на \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}.