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 10^{9}.

### Samples

input | output |
---|

2 2
..
..
| 4 |

2 2
*.
.* | 0 |

**Problem Source: **SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.