ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

## 1627. Join

Ограничение времени: 4.0 секунды
Ограничение памяти: 64 МБ
Businessman Petya recently bought a new house. This house has one floor with n × m square rooms, placed in rectangular lattice. Some rooms are pantries and the other ones are bedrooms. Now he wants to join all bedrooms with doors in such a way that there will be exactly one way between any pair of them. He can make doors only between neighbouring bedrooms (i.e. bedrooms having a common wall). Now he wants to count the number of different ways he can do it.

### Исходные данные

First line contains two integers n and m (1 ≤ n, m ≤ 9) — the number of lines and columns in the lattice. Next n lines contain exactly m characters representing house map, where "." means bedroom and "*" means pantry. It is guaranteed that there is at least one bedroom in the house.

### Результат

Output the number of ways to join bedrooms modulo 109.

### Примеры

исходные данныерезультат
```2 2
..
..
```
`4`
```2 2
*.
.*```
`0`
Источник задачи: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.