Description

lxhgww’s nickname is “Little L” (Xiao L), because he always likes L-shaped things.

Little L’s living room is an $r\times c$ rectangle. He wants to cover the entire living room with L-shaped tiles. Some positions contain pillars and cannot be tiled.

Little L wants to know how many different ways there are to tile the living room using L-shaped tiles.

Note that, as shown in the figure below, the two arms of an L-shaped tile can have any positive lengths, but neither arm can have length $0$.

After tiling, every position without a pillar must be covered by tiles, and no position may be covered more than once.

Input Format

The first line contains two integers, $r$ and $c$, representing the size of the living room.

Then follow $r$ lines, each containing $c$ characters. Each character is either _ or *. _ indicates the position is empty and must be tiled; * indicates the position has a pillar and cannot be tiled.

Output Format

Output one line containing an integer: the number of tiling schemes. Since this number can be large, print the remainder when it is divided by $20110520$.

2 2
*_
__

1

3 3
 ___
 _*_
 ___

8

Hint

Constraints

Translated by ChatGPT 5