lxhgww's nickname is "Little L," because he is very fond of L-shaped things. The living room in Little L's house is an $R \times C$ rectangle. He wants to cover the entire living room with L-shaped tiles. There are pillars in some positions in the living room where tiles cannot be placed. Little L wants to know how many different ways there are to cover the entire living room with L-shaped tiles.

Note that, as shown in the figure below, the lengths of the two arms of the L-shaped tile can vary, but neither length can be $0$. After the tiling is completed, all areas in the living room without pillars must be covered by tiles, and no area can be covered more than once.

Input

The first line of input contains two integers, $R$ and $C$, representing the size of the living room.

This is followed by $R$ lines, each containing $C$ characters. _ indicates that the corresponding position is empty and must be covered with a tile; * indicates that the corresponding position has a pillar and cannot be covered with a tile.

Output

Output a single line containing an integer representing the number of ways to cover the entire living room. Since this number may be very large, output it modulo $20110520$.

Examples

Input 1

2 2
*_
__

Output 1

1

Input 2

3 3
___
_*_
___

Output 2

8

Subtasks