Solitaire (Translated)

JOI Spring Training Camp 2015/16
Original Statement / Submission Site

Problem Statement

JOI is playing a game using a grid board that is 3 cells tall and N cells wide, along with several tokens. In the initial state of the game, some cells contain a token, and some cells do not.

The goal of the game is to place a token on each empty cell, one at a time, until all cells on the board contain a token. However, a token can only be placed on a cell if at least one of the following conditions is satisfied:

• The cells immediately above and below it both contain tokens.
• The cells immediately to the left and right of it both contain tokens.

JOI is curious to know how many different sequences of token placements can lead from the initial state to the final state where all cells are filled.

Note that the number of possible sequences can be very large, so your task is to compute the number of valid sequences modulo 1,000,000,007.

Task

Given the initial state of the game, write a program to compute the number of valid sequences to complete the board, modulo 1,000,000,007.

Input

• The first line contains an integer N – the width of the board (3 rows by N columns).
• The next 3 lines each contain a string of length N consisting of characters 'o' or 'x'.
  • 'o' means a token is placed in that cell initially.
  • 'x' means the cell is initially empty.

Output

Print a single line containing the number of valid sequences modulo 1,000,000,007.

Constraints

1 ≤ N ≤ 2,000

Subtasks

• Subtask 1 [10 points]:
  • At most 16 cells are empty in the initial state.
  • N ≤ 30
• Subtask 2 [12 points]:
  • For every empty cell, at most 2 of its adjacent cells (up/down/left/right) are also empty.
• Subtask 3 [20 points]:
  • No three vertically aligned cells are all empty.
  • N ≤ 30
• Subtask 4 [38 points]:
  • N ≤ 300
• Subtask 5 [20 points]:
  • No additional constraints.

Sample Input 1

3
oxo
xxo
oxo

Sample Output 1

14

Explanation of Output 1

The initial board state is:

o x o
x x o
o x o

There are 14 valid sequences to place the tokens and complete the board. The sequences of placements are illustrated below (numbers indicate order of placement):

o 1 o     o 1 o     o 1 o     o 1 o     o 2 o     o 2 o     o 3 o     o 4 o     o 3 o     o 4 o     o 2 o     o 2 o     o 3 o     o 4 o
2 3 o     2 4 o     3 4 o     4 3 o     1 3 o     1 4 o     1 2 o     1 2 o     1 4 o     1 3 o     3 4 o     4 3 o     2 4 o     2 3 o
o 4 o     o 3 o     o 2 o     o 2 o     o 4 o     o 3 o     o 4 o     o 3 o     o 2 o     o 2 o     o 1 o     o 1 o     o 1 o     o 1 o

Sample Input 2

10
ooxooxoxoo
xooxxxoxxx
oxoxoooooo

Sample Output 2

149022720

Sample Input 3

10
ooxoxxoxoo
oxxxxxoxxx
oxooxoxoxo

Sample Output 3

0

In this case, it is impossible to fill all cells.

Sample Input 4

20
oxooxoxooxoxooxoxoxo
oxxxoxoxxxooxxxxxoox
oxooxoxooxooxooxoxoo

Sample Output 4

228518545