CF77D.Domino Carpet

...Mike the TV greets you again!

Tired of the monotonous furniture? Sick of gray routine? Dreaming about dizzying changes in your humble abode? We have something to offer you!

This domino carpet for only $99.99 will change your life! You can lay it on the floor, hang it on the wall or even on the ceiling! Among other things ...

Having watched the commercial, virus Hexadecimal also wanted to get a Domino Carpet and wanted badly to be photographed in front of it. But of course, a virus will never consent to buying a licensed Carpet! So she ordered a truck of dominoes and decided to make such a Carpet herself.

The original Domino Carpet is a field of squares n × m in size. Each square is half of a domino, and can be rotated either vertically or horizontally, independently from its neighbors. Vertically rotated domino halves look like this:

And horizontally rotated halves look like this:

Notice, that some halves looks the same in both rotations, but other halves differ.

Dominoes bought by Hexadecimal are represented by uncuttable chips 1 × 2 in size, which can be laid either vertically or horizontally. If the chip is laid vertically, then both of it's halves should be laid vertically orientated; if the chip is laid horizontally, then both of it's halves should be laid horizontally.

The samples of valid and invalid dominoes laid vertically and horizontally are:

Virus Hexadecimal assembles her own Domino Carpet so that the following conditions are satisfied:

• each carpet square is covered by a domino chip, i.e. there are no empty squares;
• all domino chips lie entirely within the carpet and don't overlap with each other;
• if there is a horizontal domino chip with its left half in column j then there are no horizontal domino chips with their left halves in columns j - 1 or j + 1.

Before starting to assemble her own Domino Carpet, the virus wants to know the number of ways to achieve the intended purpose modulo 109 + 7.

You can assume that the virus has an infinitely large number of dominoes of each type.

……迈克电视先生再次向您问好！

厌倦了单调的家具？受够了灰暗的日常？梦想着为您的温馨小屋带来令人目眩神迷的改变？我们为您准备了特别产品！

仅售 99.99 美元的多米诺地毯，将彻底改变您的生活！您可以将其铺设于地面、悬挂于墙面，甚至倒贴在天花板上！除此之外……

病毒十六进制观看了这则广告后，也渴望拥有一块多米诺地毯，并极度渴望站在它前面拍照留念。但当然，一个病毒绝不会屈尊购买正版地毯！于是她订购了一卡车的多米诺骨牌，决心亲手制作一块属于自己的地毯。

原始的多米诺地毯是一个大小为 $n \times m$ 的方格阵列。每个方格代表一个多米诺骨牌的一半，且可独立于其邻格，选择竖直或水平方向旋转。竖直旋转的多米诺半块如下图所示：

而水平旋转的多米诺半块如下图所示：

请注意：某些半块在两种旋转方式下外观相同，而另一些则不同。

十六进制病毒所购得的多米诺骨牌，是由不可分割的 $1 \times 2$ 尺寸芯片构成，这些芯片可竖直或水平放置。若芯片竖直放置，则其两个半块均须为竖直朝向；若芯片水平放置，则其两个半块均须为水平朝向。

以下为合法与非法的竖直及水平放置多米诺骨牌示例：

病毒十六进制在组装她自己的多米诺地毯时，需满足如下条件：

• 地毯的每个方格均被恰好一块多米诺芯片覆盖，即不存在空置方格；
• 所有多米诺芯片完全位于地毯范围内，且彼此互不重叠；
• 若存在一块水平放置的多米诺芯片，其左半块位于第 $j$ 列，则不得存在任何水平放置的多米诺芯片，其左半块位于第 $j-1$ 列或第 $j+1$ 列。

在开始组装她自己的多米诺地毯之前，病毒希望知道：满足上述所有要求的铺设方案总数（对 $10^9 + 7$ 取模）是多少。

你可以假定病毒拥有每种类型的多米诺骨牌的无限供应。

The first line contains two integers n and m, separated by a space — the size of the Domino Carpet (1 ≤ n, m ≤ 250). Next 4_n_ + 1 lines contain 4_m_ + 1 symbols.

Each square of the Domino Carpet, which is a domino half, is described by a 3 × 3 square. Symbol 'O' in this square indicates the presence of a point, symbol '.' — its absence.

Each 3 × 3 square is delineated from adjacent squares by symbols '#' as shown in the examples.

It is guaranteed that every box describes the correct half of a domino.

In all pretests the Domino Carpets have the size of 2 × 2 and 4 × 4.

第一行包含两个整数 $n$ 和 $m$，以空格分隔——表示多米诺地毯的尺寸（$1 \leq n, m \leq 250$）。接下来的 $4n+1$ 行中，每行包含 $4m+1$ 个字符。

多米诺地毯中的每个正方形（即一个多米诺骨牌的一半）由一个 $3 \times 3$ 的方块描述。该方块中的字符 'O' 表示此处有一个点，字符 '.' 表示此处无点。

每个 $3 \times 3$ 方块均通过字符 '#' 与相邻方块分隔，如示例所示。

保证每个方块都正确描述了一个多米诺骨牌的一半。

在所有预测试用例中，多米诺地毯的尺寸均为 $2 \times 2$ 和 $4 \times 4$。

Print a single number, the number of ways to assemble the Domino Carpet modulo 109 + 7, using only standard dominoes of size 1 × 2.

输出一个整数，表示仅使用标准的 $1 \times 2$ 多米诺骨牌拼成多米诺地毯的方案数，结果对 $10^9 + 7$ 取模。

A note to the first example: all correct ways to make Domino Carpet are represented below:

And this way is incorrect:

第一个样例的说明：所有正确的多米诺骨牌地毯构造方式如下所示：

而以下这种方式是错误的：