D. 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 #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: 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 #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. 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: Before 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]. You can assume that the virus has an infinitely large number of dominoes of each type. 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]. 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]. *A note to the first example:* all correct ways to make Domino Carpet are represented below: And this way is incorrect: ## Input 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]. ## Output 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]. [samples] ## Note *A note to the first example:* all correct ways to make Domino Carpet are represented below: And this way is incorrect:

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the dimensions of the grid, where $ 1 \leq n, m \leq 250 $. The Domino Carpet is a grid of $ n \times m $ cells, each cell representing a half-domino. Each 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. Let $ 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: - A half-domino can be oriented **vertically** if its pattern matches the expected visual form of a vertical half-domino. - A half-domino can be oriented **horizontally** if its pattern matches the expected visual form of a horizontal half-domino. A domino tile is a $ 1 \times 2 $ chip covering two adjacent half-dominoes: - **Vertical domino**: covers two vertically adjacent cells $ (i,j) $ and $ (i+1,j) $, both must be oriented vertically. - **Horizontal domino**: covers two horizontally adjacent cells $ (i,j) $ and $ (i,j+1) $, both must be oriented horizontally. **Constraints** 1. Every cell $ (i,j) $ must be covered by exactly one domino. 2. Each domino must cover two adjacent cells (horizontally or vertically). 3. For each domino covering cells $ (i,j) $ and $ (i',j') $: - 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). - The orientation of each half-domino must be in its allowed set $ P_{i,j} $. 4. The entire $ n \times m $ grid must be perfectly tiled with dominoes (no overlaps, no gaps). **Objective** Compute the number of valid domino tilings of the $ n \times m $ grid satisfying the above constraints, modulo $ 10^9 + 7 $.