Xenia非常喜欢拼图。她特别喜欢由多米诺骨牌组成的拼图。看一下显示此类谜题之一的图片。
拼图是一个 3 × n 的表格,其中包含包含多米诺骨牌(图片上的彩色矩形)的禁止单元(黑色方块)。如果一个谜题满足以下条件,则该谜题被称为正确:
- 每个多米诺骨牌正好占据表格的两个非禁止单元格;
- 没有两个多米诺骨牌占据同一个表格单元格;
- 表格中恰好有一个非禁止单元格未被任何多米诺骨牌占据(在图中用圆圈标记)。
要解决这个难题,您需要多个步骤将空单元格从起始位置传输到某个指定位置。如果谜题保持正确,则移动是将多米诺骨牌运送到空单元格。水平多米诺骨牌只能水平移动,垂直多米诺骨牌只能垂直移动。你无法旋转多米诺骨牌。图中显示了可能的举动。
Xenia 有一个 3 × n 的表格,其中包含禁止单元格和标有圆圈的单元格。另外,Xenia 有很多相同的多米诺骨牌。现在,Xenia 想知道,如果她将多米诺骨牌放在现有的桌子上,她可以制作出多少个不同的正确谜题。此外,Xenia 希望最终拼图中圆圈标记的单元格为空。该谜题必须至少包含一个动作。
帮助 Xenia,计算所描述的谜题数量。由于描述的数字可能相当大,因此打印除以 1000000007 (109 + 7) 后的余数。
输入
第一行包含整数 n (3 ≤ n ≤ 104) — 拼图的大小。以下三行每行包含 n 个字符——表的描述。如果对应的单元格是禁止的,则第 i 行的第 j 个字符等于“X”;如果相应的单元格是非禁止的,则它等于“.”;如果相应的单元格标有圆圈,则它等于“O”。
保证表格中恰好有一个单元格被标记为圆圈。保证给定表格中与标记单元格至少有一个公共点的所有单元格都是非禁止的。
输出
打印一个数字——问题的答案以 1000000007 (109 + 7) 为模。
示例
输入 #1
5 ....X .O... ...X.
输出 #1
1
输入 #2
5 ..... .O... .....
输出 #2
2
输入 #3
3 ... ... ..O
输出 #3
4
注意
如果有一对单元格在一个谜题中包含一个多米诺骨牌,而在另一个谜题中不包含它,则认为两个谜题是不同的。