P3272 [SCOI2011] Floor

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.

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 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$.

#### Constraints | Test point ID | Limits | | :----------: | :----------: | | $1\sim 2$ | $1\le r\times c\le 25$ | | $3\sim 5$ | $1\le r\times c\le 100$ and ($r=2$ or $c=2$) | | $6\sim 10$ | $1\le r\times c\le 100$ | Translated by ChatGPT 5