Rooms

Businessman Petya has recently purchased a new house. This house consists of a single floor, divided into (n $\times$ m) identical square rooms. Some of these rooms will serve as living rooms, while others will be used as storage rooms.

Petya wants to create passages between certain living rooms so that any living room can be reached from any other living room through these passages, and there should be exactly one unique path between any two living rooms. Passages can only be established between adjacent rooms, meaning rooms that share a common wall.

Your task is to determine the number of different ways to connect the living rooms as described.

Input

The first line of the input contains the integers (n) and (m) ((1 $\le$ n, m $\le$ 12)). Following this, there are (n) lines, each containing (m) characters, which represent the layout of the house. The character "." denotes a living room, while "*" denotes a storage room.

Output

Output a single integer — the remainder when the number of ways to connect the rooms is divided by (10^9).

Examples