...迈克电视再次向您问好!
厌倦了单调的家具?厌倦了灰色的日常?梦想着你简陋的住所发生令人眼花缭乱的变化吗?我们有东西可以提供给您!
这款多米诺骨牌地毯仅需 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
注意
第一个示例的注释:制作多米诺地毯的所有正确方法如下所示:
这种方式是不正确的: