{"raw_statement":[{"iden":"statement","content":"_...Mike the TV greets you again!_\n\n_Tired of the monotonous furniture? Sick of gray routine? Dreaming about dizzying changes in your humble abode? We have something to offer you!_\n\n_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 ..._\n\nHaving 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.\n\nThe 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:\n\nAnd horizontally rotated halves look like this:\n\nNotice, that some halves looks the same in both rotations, but other halves differ.\n\nDominoes 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.\n\nThe samples of valid and invalid dominoes laid vertically and horizontally are:\n\nVirus Hexadecimal assembles her own Domino Carpet so that the following conditions are satisfied:\n\n* each carpet square is covered by a domino chip, i.e. there are no empty squares;\n* all domino chips lie entirely within the carpet and don't overlap with each other;\n* 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.\n\nBefore starting to assemble her own Domino Carpet, the virus wants to know the number of ways to achieve the intended purpose modulo 109 + 7.\n\nYou can assume that the virus has an infinitely large number of dominoes of each type."},{"iden":"input","content":"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.\n\nEach 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.\n\nEach 3 × 3 square is delineated from adjacent squares by symbols _'#'_ as shown in the examples.\n\nIt is guaranteed that every box describes the correct half of a domino.\n\nIn all pretests the Domino Carpets have the size of 2 × 2 and 4 × 4."},{"iden":"output","content":"Print a single number, the number of ways to assemble the Domino Carpet modulo 109 + 7, using only standard dominoes of size 1 × 2."},{"iden":"examples","content":"Input\n\n3 4\n#################\n#O..#...#O.O#...#\n#.O.#.O.#.O.#...#\n#..O#...#O.O#...#\n#################\n#O.O#OOO#O.O#...#\n#.O.#...#...#.O.#\n#O.O#OOO#O.O#...#\n#################\n#O.O#...#O.O#...#\n#...#...#...#.O.#\n#O.O#...#O.O#...#\n#################\n\nOutput\n\n3\n\nInput\n\n2 2\n#########\n#O.O#O.O#\n#.O.#...#\n#O.O#O.O#\n#########\n#...#O.O#\n#...#...#\n#...#O.O#\n#########\n\nOutput\n\n2\n\nInput\n\n2 2\n#########\n#..O#O..#\n#...#...#\n#O..#..O#\n#########\n#O..#..O#\n#...#...#\n#..O#O..#\n#########\n\nOutput\n\n0"},{"iden":"note","content":"**A note to the first example:** all correct ways to make Domino Carpet are represented below:\n\nAnd this way is incorrect:\n\n"}],"translated_statement":[{"iden":"statement","content":"_...Mike the TV greets you again!_ \n\n_Tired of the monotonous furniture? Sick of gray routine? Dreaming about dizzying changes in your humble abode? We have something to offer you!_ \n\n_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 ..._ \n\nHaving 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. \n\nThe original Domino Carpet is a field of squares #cf_span[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: \n\nAnd horizontally rotated halves look like this: \n\nNotice, that some halves looks the same in both rotations, but other halves differ.\n\nDominoes bought by Hexadecimal are represented by uncuttable chips #cf_span[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.\n\nThe samples of valid and invalid dominoes laid vertically and horizontally are: \n\nVirus Hexadecimal assembles her own Domino Carpet so that the following conditions are satisfied:\n\nBefore starting to assemble her own Domino Carpet, the virus wants to know the number of ways to achieve the intended purpose modulo #cf_span[109 + 7].\n\nYou can assume that the virus has an infinitely large number of dominoes of each type.\n\nThe first line contains two integers #cf_span[n] and #cf_span[m], separated by a space — the size of the Domino Carpet (#cf_span[1 ≤ n, m ≤ 250]). Next #cf_span[4n + 1] lines contain #cf_span[4m + 1] symbols. \n\nEach square of the Domino Carpet, which is a domino half, is described by a #cf_span[3 × 3] square. Symbol _'O'_ in this square indicates the presence of a point, symbol _'.'_ — its absence. \n\nEach #cf_span[3 × 3] square is delineated from adjacent squares by symbols _'#'_ as shown in the examples. \n\nIt is guaranteed that every box describes the correct half of a domino. \n\nIn all pretests the Domino Carpets have the size of #cf_span[2 × 2] and #cf_span[4 × 4].\n\nPrint a single number, the number of ways to assemble the Domino Carpet modulo #cf_span[109 + 7], using only standard dominoes of size #cf_span[1 × 2].\n\n*A note to the first example:* all correct ways to make Domino Carpet are represented below:\n\nAnd this way is incorrect:\n\n"},{"iden":"input","content":"The first line contains two integers #cf_span[n] and #cf_span[m], separated by a space — the size of the Domino Carpet (#cf_span[1 ≤ n, m ≤ 250]). Next #cf_span[4n + 1] lines contain #cf_span[4m + 1] symbols. Each square of the Domino Carpet, which is a domino half, is described by a #cf_span[3 × 3] square. Symbol _'O'_ in this square indicates the presence of a point, symbol _'.'_ — its absence. Each #cf_span[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 #cf_span[2 × 2] and #cf_span[4 × 4]."},{"iden":"output","content":"Print a single number, the number of ways to assemble the Domino Carpet modulo #cf_span[109 + 7], using only standard dominoes of size #cf_span[1 × 2]."},{"iden":"examples","content":"Input3 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#...##################Output3Input2 2##########O.O#O.O##.O.#...##O.O#O.O###########...#O.O##...#...##...#O.O##########Output2Input2 2##########..O#O..##...#...##O..#..O###########O..#..O##...#...##..O#O..##########Output0"},{"iden":"note","content":"*A note to the first example:* all correct ways to make Domino Carpet are represented below: And this way is incorrect: "}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the grid, where $ 1 \\leq n, m \\leq 250 $. \nThe Domino Carpet is a grid of $ n \\times m $ cells, each cell representing a half-domino. \nEach cell $ (i, j) $, for $ 1 \\leq i \\leq n $, $ 1 \\leq j \\leq m $, is associated with a $ 3 \\times 3 $ pattern of symbols from $ \\{ \\texttt{.}, \\texttt{O}, \\texttt{\\#} \\} $, encoding the configuration of dots (points) on that half-domino. \nLet $ P_{i,j} \\subseteq \\{ \\text{vertical}, \\text{horizontal} \\} $ denote the set of valid orientations for the half-domino at $ (i,j) $, determined by its $ 3 \\times 3 $ pattern: \n- A half-domino can be oriented **vertically** if its pattern matches the expected visual form of a vertical half-domino. \n- A half-domino can be oriented **horizontally** if its pattern matches the expected visual form of a horizontal half-domino. \n\nA domino tile is a $ 1 \\times 2 $ chip covering two adjacent half-dominoes: \n- **Vertical domino**: covers two vertically adjacent cells $ (i,j) $ and $ (i+1,j) $, both must be oriented vertically. \n- **Horizontal domino**: covers two horizontally adjacent cells $ (i,j) $ and $ (i,j+1) $, both must be oriented horizontally. \n\n**Constraints** \n1. Every cell $ (i,j) $ must be covered by exactly one domino. \n2. Each domino must cover two adjacent cells (horizontally or vertically). \n3. For each domino covering cells $ (i,j) $ and $ (i',j') $: \n - The orientation of both half-dominoes must be consistent with the domino’s direction (i.e., both vertical for a vertical domino, both horizontal for a horizontal domino). \n - The orientation of each half-domino must be in its allowed set $ P_{i,j} $. \n4. The entire $ n \\times m $ grid must be perfectly tiled with dominoes (no overlaps, no gaps). \n\n**Objective** \nCompute the number of valid domino tilings of the $ n \\times m $ grid satisfying the above constraints, modulo $ 10^9 + 7 $.","simple_statement":null,"has_page_source":false}