No.226 0-1パズル

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 18
作問者 : drken1215drken1215

2 ProblemId : 600 / 出題時の順位表

問題文

縦\(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

提出ページヘ