ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Join

Time limit: 4.0 second
Memory limit: 64 MB
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.

Input

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

Output the number of ways to join bedrooms modulo 109.

Samples

inputoutput
2 2
..
..
4
2 2
*.
.*
0
Problem Source: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.
To submit the solution for this problem go to the Problem set: 1627. Join