题目描述

题目译自 JOISC 2016 Day1 T3 「ソリティア」

JOI 君有一个棋盘，棋盘上有 $N$ 行 $3$ 列 的格子。JOI 君有若干棋子，并想用它们来玩一个游戏。初始状态棋盘上至少有一个棋子，也至少有一个空位。

游戏的目标是：在还没有放棋子的格子上依次放棋子，并填满整个棋盘。在某个格子上放置棋子必须满足以下条件之一：

1. 这个格子的上下一格都放有棋子；
2. 这个格子的左右一格都放有棋子。

JOI 君想知道有多少种从初始状态开始，并达到游戏目标的方案，这个答案可能会非常大。请你帮 JOI 君算出这个答案，并对 $10^9+7$ 取模。

输入格式

第一行有一个整数 $N$ ，表示棋盘的大小为纵向 $3$ 格，横向 $N$ 格。

接下来的三行均为仅由 o 和 x 组成的字符串。这三行中第 $i$ 行的第 $j$ 个字符表示棋盘中从上到下第 $i$ 行，从左到右第 $j$ 个棋子的状态。其中 o 表示开始时有棋子被放置，x 表示开始时这个位置为没有放置着棋子。

输出格式

一个整数，表示符合条件的方案个数。

3
oxo
xxo
oxo

14

10
ooxooxoxoo
xooxxxoxxx
oxoxoooooo

149022720

10
ooxoxxoxoo
oxxxxxoxxx
oxooxoxoxo

0

20
oxooxoxooxoxooxoxoxo
oxxxoxoxxxooxxxxxoox
oxooxoxooxooxooxoxoo

228518545

数据范围与提示

对于所有数据，满足 $1 \le N \le 2000$。