17706번 - Solitaire 서브태스크다국어

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．

• ゲームの初期状態において，コマの置かれていないマスの個数は 16 個以下である．
• N ≦ 30．

• ゲームの初期状態において，コマの置かれていない各マスについて，そのマスに上下左右に隣り合う マスのうちコマの置かれていないマスの個数が 2 個以下である．

• ゲームの初期状態において，コマの置かれていないマスが縦に 3 個連続して並ぶことはない．
• N ≦ 30．

• N ≦ 300 を満たす．

追加の制約はない．