JOI 君正在使用一个纵向 3 格、横向 $N$ 格的网格棋盘和一些棋子进行游戏。 在游戏的初始状态下，至少有一个格子放置了棋子，且至少有一个格子没有放置棋子。 这个游戏的目标是通过在没有棋子的格子上逐个放置棋子，使得棋盘上的所有格子都放有棋子。但是，在一个格子上放置棋子的条件是必须满足以下条件之一：

• 该格子的正上方和正下方的两个格子都已经放置了棋子。
• 该格子的正左方和正右方的两个格子都已经放置了棋子。

JOI 君想知道，从游戏的初始状态开始，直到达成目标为止，放置棋子的顺序总共有多少种。注意，这个值可能会非常大。 你的任务是代替 JOI 君，求出从游戏初始状态到达成目标为止，放置棋子的顺序数量，并将其对 $1\,000\,000\,007$ 取模。

题目描述

给定游戏的初始状态，编写一个程序，求出达成目标为止放置棋子的顺序数量，并将其对 $1\,000\,000\,007$ 取模。

输入格式

从标准输入读取以下数据：

• 第 1 行包含一个整数 $N$。这表示游戏所使用的棋盘大小为纵向 3 格，横向 $N$ 格。
• 接下来的 3 行，每行包含一个长度为 $N$ 的字符串。每个字符为 ‘o’ 或 ‘x’。这 3 行中的第 $i$ 行 ($1 \le i \le 3$) 的从左往右第 $j$ 个字符 ($1 \le j \le N$) 表示棋盘从上往下第 $i$ 行、从左往右第 $j$ 列的格子的初始状态。如果该字符为 ‘o’，则表示在游戏的初始状态下该格子已经放置了棋子。如果为 ‘x’，则表示在游戏的初始状态下该格子没有放置棋子。

输出格式

将达成目标为止放置棋子的顺序数量对 $1\,000\,000\,007$ 取模后的结果输出到标准输出。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 2\,000$。

子任务

子任务 1 [10 点]

满足以下条件： 在游戏的初始状态下，没有放置棋子的格子数量不超过 16 个。 $N \le 30$。

子任务 2 [12 点]

• 在游戏的初始状态下，对于每个没有放置棋子的格子，其上下左右相邻的格子中，没有放置棋子的格子数量不超过 2 个。

子任务 3 [20 点]

满足以下条件： 在游戏的初始状态下，没有放置棋子的格子不会在纵向上连续出现 3 个。 $N \le 30$。

子任务 4 [38 点]

• 满足 $N \le 300$。

子任务 5 [20 点]

• 没有额外限制。

样例

样例 1

输入：

3
oxo
xxo
oxo

输出：

14

样例 2

输入：

10
ooxooxoxoo
xooxxxoxxx
oxoxoooooo

输出：

149022720

样例 3

输入：

10
ooxoxxoxoo
oxxxxxoxxx
oxooxoxoxo

输出：

0

样例 4

输入：

20
oxooxoxooxoxooxoxoxo
oxxxoxoxxxooxxxxxoox
oxooxoxooxooxooxoxoo

输出：

228518545

说明

样例 3 说明了根据游戏的初始状态，有时可能无法达成目标。