시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 4 4 4 100.000%

문제

JOI 君は,縦に 3 マス,横に N マスの方眼状のボードと,いくつかのコマを使ってゲームをしている. ゲームの初期状態において,1 個以上のマスにはコマが置かれており,また,1 個以上のマスにはコマが置 かれていない.

このゲームの目的は,コマの置かれていないマスにコマを 1 個ずつ置いていくことで,ボード上のすべ てのマスにコマが置かれた状態にすることである.ただし,あるマスにコマを置ける条件は,以下のいず れかが満たされることである.

  • そのマスの一つ上のマスと一つ下のマスの両方にコマが置かれている.
  • そのマスの一つ左のマスと一つ右のマスの両方にコマが置かれている.

JOI 君はゲームの初期状態から始めて,目的を達成するまでにコマを置いていく順番が全部で何通りあ るのかが気になった.ただしこの値は非常に大きくなることがある.

あなたの課題は,JOI 君の代わりに,ゲームの初期状態から目的を達成するまでにコマを置いていく順 番の個数を 1 000 000 007 で割った余りを求めることである.

ゲームの初期状態が与えられたとき,目的を達成するまでにコマを置いていく順番の個数を 1 000 000 007 で割った余りを求めるプログラムを作成せよ.

입력

標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N が書かれている.これは,ゲームで使うボードの大きさが,縦に 3 マス,横に N マスであることを表す.
  • 続く 3 行のそれぞれには,N 文字からなる文字列が書かれている.各文字は ‘o’ もしくは ‘x’ である. この 3 行のうちの i 行目 (1 ≦ i ≦ 3) の左から j 文字目 (1 ≦ j ≦ N) は,ボードの上から i 行目,左か ら j 列目のマスの初期状態を表す.この文字が ‘o’ のときは,ゲームの初期状態においてそのマスに コマが置かれていることを表す.また,‘x’ のときは,ゲームの初期状態においてそのマスにコマが 置かれていないことを表す.

출력

標準出力に,目的を達成するまでにコマを置いていく順番の個数を 1 000 000 007 で割った余りを 1 行で 出力せよ.

제한

  • 1 ≦ N ≦ 2 000.

예제 입력 1

3
oxo
xxo
oxo

예제 출력 1

14

この入力例では,ゲームの初期状態は以下の通りである (コマの置かれたマスを○で表す).

次のいずれかの表に従ってコマを置いていくことで,目的を達成することができる (番号はコマを置い ていく順番を表す).

目的を達成する順番はこれらの 14 通りのみであるので,14 を出力する.

예제 입력 2

10
ooxooxoxoo
xooxxxoxxx
oxoxoooooo

예제 출력 2

149022720

예제 입력 3

10
ooxoxxoxoo
oxxxxxoxxx
oxooxoxoxo

예제 출력 3

0

ゲームの初期状態によっては,目的を達成できないこともある.

예제 입력 4

20
oxooxoxooxoxooxoxoxo
oxxxoxoxxxooxxxxxoox
oxooxoxooxooxooxoxoo

예제 출력 4

228518545