← 返回题目列表

Codeforces · 77/D

D. 多米诺地毯

中文机器翻译题面 查看原题

...迈克电视再次向您问好!

厌倦了单调的家具?厌倦了灰色的日常?梦想着你简陋的住所发生令人眼花缭乱的变化吗?我们有东西可以提供给您!

这款多米诺骨牌地毯仅需 99.99 美元,将改变您的生活!您可以将它放在地板上、挂在墙上甚至天花板上!除其他事项外...

病毒十六进制看完广告后也想得到一块多米诺地毯,并且非常想在它前面拍照。但当然,病毒永远不会同意购买经过许可的地毯!于是她订购了一卡车多米诺骨牌,并决定自己制作这样的地毯。

最初的多米诺地毯是一块大小为 n × m 的正方形区域。每个方块都是多米诺骨牌的一半,可以垂直或水平旋转,独立于其邻居。垂直旋转的多米诺骨牌两半看起来像这样:

水平旋转的两半看起来像这样:

请注意,某些半部在两次旋转中看起来相同,但其他半部则不同。

十六进制购买的多米诺骨牌是用不可切割的1×2尺寸的木片来表示的,可以垂直或水平放置。如果芯片是垂直放置的,那么它的两半都应该垂直放置;如果芯片是水平放置的,那么它的两半都应该水平放置。

垂直和水平放置的有效和无效多米诺骨牌样本为:

病毒十六进制组装她自己的多米诺地毯,以满足以下条件:

- 每个地毯方块都被多米诺骨牌覆盖,即没有空方块;
- 所有多米诺骨牌完全位于地毯内,并且彼此不重叠;
- 如果存在左半部分在 j 列中的水平多米诺骨牌筹码,则不存在其左半部分在 j - 1 或 j + 1 列中的水平多米诺骨牌筹码。

在开始组装自己的多米诺地毯之前,病毒想知道达到预期目的模 109 + 7 的方法数。

您可以假设该病毒具有无限数量的每种类型的多米诺骨牌。

输入

第一行包含两个整数 n 和 m,用空格分隔 — 多米诺地毯的大小 (1 ≤ n,m ≤ 250)。接下来的 4n + 1 行包含 4m + 1 个符号。

多米诺地毯的每个方格(即半张多米诺骨牌)由 3 × 3 方格描述。该方块中的符号“O”表示点的存在,符号“.” ——它的缺席。

每个 3 × 3 的正方形都用符号“#”与相邻的正方形划分,如示例中所示。

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

在所有预测试中,多米诺地毯的尺寸为 2 × 2 和 4 × 4。

输出

仅使用尺寸为 1 × 2 的标准多米诺骨牌,打印单个数字,以 109 + 7 为模组装多米诺地毯的方式数。

示例

输入 #1

3 4
#################
#O..#...#O.O#...#
#.O.#.O.#.O.#...#
#..O#...#O.O#...#
#################
#O.O#OOO#O.O#...#
#.O.#...#...#.O.#
#O.O#OOO#O.O#...#
#################
#O.O#...#O.O#...#
#...#...#...#.O.#
#O.O#...#O.O#...#
#################

输出 #1

3

输入 #2

2 2
#########
#O.O#O.O#
#.O.#...#
#O.O#O.O#
#########
#...#O.O#
#...#...#
#...#O.O#
#########

输出 #2

2

输入 #3

2 2
#########
#..O#O..#
#...#...#
#O..#..O#
#########
#O..#..O#
#...#...#
#..O#O..#
#########

输出 #3

0

注意

第一个示例的注释:制作多米诺地毯的所有正确方法如下所示:

这种方式是不正确的: