eolymp
bolt
Try our new interface for solving problems
Problems

Комнаты

Комнаты

Time limit 3 seconds
Memory limit 256 MiB

Бизнесмен Петя недавно купил новый дом. В этом доме один этаж, разделённый на n×m одинаковых по размеру квадратных комнат, некоторые из которых будут жилыми, а в некоторых будут расположены кладовые.

Петя хочет, чтобы между некоторыми жилыми комнатами были проходы, и чтобы из любой жилой комнаты можно было добраться в любую другую жилую комнату, используя эти проходы, причём единственным образом. Проходы можно делать только между соседними комнатами, т.е. между теми, у которых есть общая стена.

Требуется посчитать количество различных способов соединить комнаты требуемым образом.

Input data

В первой строке входного файла содержатся числа n и m (1n, m12). Далее следуют n строк по m символов в каждой, представляющие собой карту дома. Символ "." соответствует жилой комнате, а "*" соответствует кладовой.

Output data

Выведите одно число — остаток от деления искомого количества на 10^9.

Examples

Input example #1
2 2
..
..
Output example #1
4
Source III International Summer School Programming in Sevastopol 2012