No.226 0-1パズル
drken1215問題文
縦\(H\), 横\(W\)のマスからなる長方形があり、各マスには'0'か'1'か'?'のいずれかが書かれている。
今、'?'の書かれている全てのマスに対し、以下の条件を満たすように、'?'を消して'0'か'1'を書き込みたい。
そのような方法のパターン数を mod. 1000000007 で求めるプログラムを書いて下さい。
(条件)
どの2×2の正方形ボードを取り出しても、0が丁度2個、1が丁度2個含まれている。
より正確には、ボードの上から\(i\)番目 (1-index)、左から\(j\)番目 (1-index) のマスの値を\(v(i, j)\)と表したとき、
任意の \(1 \leq i \leq H-1\), \(1 \leq j \leq W-1\) に対し、4個の値 \(v(i, j), v(i, j+1), v(i+1, j), v(i+1, j+1)\) のうち、
丁度2個が'0'で、丁度2個が'1'となっている。
入力
\(H\) \(W\) \(S_1\) \(S_2\) ⋮ \(S_H\)
一行目に\(H\), \(W\)がスペース区切りで与えられます。
続く\(H\)行には、マスの\(i\)行目の塗られかたを表す長さ\(W\)の文字列\(S_i\)が与えられます。
\(2 \leq H \leq 100\)
\(2 \leq W \leq 100\)
\(S_i\)は、'0'と'1'と'?'のみから構成される文字列である
出力
パターン数 mod. 1000000007 を出力して下さい。
出力した後には改行して下さい。
サンプル
サンプル1
入力
2 4 ?11? ???0
出力
2
以下の2通りがあります。
0111 1111
1000 0000
サンプル2
入力
3 3 1?? ??0 ???
出力
3以下の3通りがあります。
101 101 111
010 010 000
101 010 111
サンプル3
入力
50 50 1????????????????????????????????????????????????0 ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? 0????????????????????????????????????????????????1
出力
949480668
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。