You have suddenly acquired a large house with several rooms. In fact, your house can be viewed as a grid of $n \times m$ cells, where each cell is either a room or a pillar. Initially, there is a wall between every pair of adjacent cells.

You want to break down some walls between adjacent rooms so that all rooms are reachable from one another. During this process, you cannot break through the exterior of the house, nor can you break through any pillars (or the walls adjacent to pillars). Additionally, you do not want it to be difficult to catch a thief in the house, so you want there to be exactly one path between any two rooms. Now, you want to calculate the total number of feasible schemes.

Input

The first line contains two integers $n$ and $m$.

The next $n$ lines each contain $m$ characters, where each character is either '.' or '', with '.' representing a room and '' representing a pillar.

Output

Output a single integer representing the number of valid schemes.

Constraints

• For the first 20% of the data, $n, m \le 3$.
• For the first 50% of the data, $n, m \le 5$.
• For 100% of the data, $n, m \le 9$.
• 40% of the data guarantees $\min(n, m) \le 3$.
• 30% of the data guarantees there are no pillars.
• Note: The answer should be taken modulo $1\,000\,000\,000$.

Examples

Input 1

2 2
..
..

Output 1

4

Input 2

2 2
*.
.*

Output 2

0