Solitaire
시간 제한4초메모리 제한512 MB
3×N 보드의 빈 칸을 채우는 순서의 수를 구한다. 어떤 칸은 위아래 칸이 모두 채워졌거나 좌우 칸이 모두 채워졌을 때만 놓을 수 있다. 경우의 수를 1e9+7로 나눈 나머지를 출력한다.
문제
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．