JOI is playing a game using a grid-shaped board with 3 rows and $N$ columns, and several pieces. In the initial state of the game, one or more squares have pieces placed on them, and one or more squares do not have pieces placed on them.

The goal of this game is to reach a state where all squares on the board have pieces by placing pieces one by one into the squares that do not currently have them. However, a piece can only be placed in a square if at least one of the following conditions is met:

• Pieces are placed in both the square immediately above and the square immediately below the target square.
• Pieces are placed in both the square immediately to the left and the square immediately to the right of the target square.

JOI is curious about the total number of different sequences in which pieces can be placed to reach the goal, starting from the initial state. Note that this value can be very large.

Your task is to write a program that, given the initial state of the game, calculates the number of sequences in which pieces can be placed to reach the goal, modulo $1\,000\,000\,007$.

Input

Read the following data from standard input:

• The first line contains an integer $N$. This represents the size of the board used in the game, which is 3 rows and $N$ columns.
• Each of the following 3 lines contains a string of length $N$. Each character is either 'o' or 'x'. The $j$-th character ($1 \le j \le N$) of the $i$-th line ($1 \le i \le 3$) represents the initial state of the square at the $i$-th row from the top and $j$-th column from the left. If this character is 'o', it means a piece is placed on that square in the initial state. If it is 'x', it means no piece is placed on that square in the initial state.

Output

Output the number of sequences in which pieces can be placed to reach the goal, modulo $1\,000\,000\,007$, on a single line.

Constraints

All input data satisfies the following condition:

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

Subtasks

Subtask 1 [10 points]

The following conditions are satisfied: In the initial state of the game, the number of squares without pieces is 16 or less. $N \le 30$.

Subtask 2 [12 points]

• In the initial state of the game, for each square without a piece, the number of squares without pieces that are adjacent (up, down, left, or right) to it is 2 or less.

Subtask 3 [20 points]

The following conditions are satisfied: In the initial state of the game, there are no 3 squares without pieces arranged vertically. $N \le 30$.

Subtask 4 [38 points]

• $N \le 300$.

Subtask 5 [20 points]

There are no additional constraints.

Examples

Input 1

3
oxo
xxo
oxo

Output 1

14

Input 2

10
ooxooxoxoo
xooxxxoxxx
oxoxoooooo

Output 2

149022720

Input 3

10
ooxoxxoxoo
oxxxxxoxxx
oxooxoxoxo

Output 3

0

Note

Depending on the initial state of the game, it may not be possible to reach the goal.

Input 4

20
oxooxoxooxoxooxoxoxo
oxxxoxoxxxooxxxxxoox
oxooxoxooxooxooxoxoo

Output 4

228518545