CF342D.Xenia and Dominoes

Xenia likes puzzles very much. She is especially fond of the puzzles that consist of domino pieces. Look at the picture that shows one of such puzzles.

A puzzle is a 3 × n table with forbidden cells (black squares) containing dominoes (colored rectangles on the picture). A puzzle is called correct if it meets the following conditions:

• each domino occupies exactly two non-forbidden cells of the table;
• no two dominoes occupy the same table cell;
• exactly one non-forbidden cell of the table is unoccupied by any domino (it is marked by a circle in the picture).

To solve the puzzle, you need multiple steps to transport an empty cell from the starting position to some specified position. A move is transporting a domino to the empty cell, provided that the puzzle stays correct. The horizontal dominoes can be moved only horizontally, and vertical dominoes can be moved only vertically. You can't rotate dominoes. The picture shows a probable move.

Xenia has a 3 × n table with forbidden cells and a cell marked with a circle. Also, Xenia has very many identical dominoes. Now Xenia is wondering, how many distinct correct puzzles she can make if she puts dominoes on the existing table. Also, Xenia wants the circle-marked cell to be empty in the resulting puzzle. The puzzle must contain at least one move.

Help Xenia, count the described number of puzzles. As the described number can be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

泽妮娅非常喜欢谜题，尤其钟爱由多米诺骨牌组成的谜题。请看下图所示的其中一个谜题：

一个谜题是一个 $3 \times n$ 的表格，其中包含若干禁止放置的格子（黑色方块），并填入了若干多米诺骨牌（图中着色的矩形）。若一个谜题满足以下条件，则称其为正确的：

• 每个多米诺骨牌恰好占据表格中两个非禁止格子；
• 任意两个多米诺骨牌不占据同一个表格格子；
• 表格中恰好有一个非禁止格子未被任何多米诺骨牌占据（图中用圆圈标出）。

求解该谜题需通过若干步操作，将空格（即未被占据的格子）从初始位置移动到某个指定位置。一次移动指：将一块与空格相邻的多米诺骨牌整体移入空格所在位置，且移动后谜题仍保持正确。水平放置的多米诺骨牌只能水平移动，垂直放置的多米诺骨牌只能垂直移动；不允许旋转多米诺骨牌。图中展示了一次可能的移动。

泽妮娅拥有一张 $3 \times n$ 的表格，其中已标出禁止格子和一个用圆圈标记的格子。此外，她拥有大量完全相同的多米诺骨牌。现在泽妮娅想知道：在该表格上放置多米诺骨牌，能构成多少种不同的正确谜题？要求：圆圈标记的格子在最终谜题中必须为空；且该谜题至少存在一步合法移动。

请帮助泽妮娅计算满足上述条件的谜题数量。由于该数目可能非常大，请输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。

The first line contains integer n (3 ≤ n ≤ 104) — the puzzle's size. Each of the following three lines contains n characters — the description of the table. The j-th character of the i-th line equals "X" if the corresponding cell is forbidden; it equals ".", if the corresponding cell is non-forbidden and "O", if the corresponding cell is marked with a circle.

It is guaranteed that exactly one cell in the table is marked with a circle. It is guaranteed that all cells of a given table having at least one common point with the marked cell is non-forbidden.

第一行包含一个整数 $n$（$3 \leq n \leq 10^4$）—— 表示谜题的尺寸。接下来三行，每行包含 $n$ 个字符，描述该表格。第 $i$ 行的第 $j$ 个字符为 "X" 表示对应格子被禁止；为 "." 表示对应格子未被禁止；为 "O" 表示对应格子标有一个圆圈。

保证表格中恰好有一个格子标有圆圈。还保证：与标有圆圈的格子至少有一个公共点（即八连通意义下相邻，含对角线）的所有格子均未被禁止。

Print a single number — the answer to the problem modulo 1000000007 (109 + 7).

输出一个数字——该问题答案对 1000000007（$10^9 + 7$）取模的结果。

Two puzzles are considered distinct if there is a pair of cells that contain one domino in one puzzle and do not contain it in the other one.

如果存在一对格子，其中一个谜题中这两个格子被一个骨牌覆盖，而另一个谜题中这两个格子未被同一个骨牌覆盖，则认为这两个谜题是不同的。