Mod 3 Knights Out

Time Limit : 1 sec, Memory Limit : 65536 KB

問題 J Mod 3 Knights Out

問題文

ある日の夕方,コンテストの問題を解き終えた二人は今日の問題について話し合っていた.
A「くそー,あのライツアウトの問題,mod 2 じゃなくて mod 3 とか mod 7 とかだったら解法分かったのにー!」
B「じゃあ,mod 3 で別の方法で解く問題を作ればいいんですね.分かりました!」
こうして次のような問題が誕生した.

H × W のチェス盤がある.チェス盤の各マスには 0 から 2 の整数が書かれている.このチェス盤にナイトを置いていく.ただし,各マスには多くても 1 体のナイトしか置けない.各マスについて,(マスの数値+そこを攻撃するマスにいるナイトの数)=0 mod 3が成り立つようなナイトの配置を良い配置と呼ぶ.攻撃するマスとはそのマスから縦方向に ±2 マスかつ横方向に ±1 マス,もしくは縦方向に ±1 マスかつ横方向に ±2 マスずれたマスのことである.

良いナイトの配置の数を求めよ.答えは大きくなる可能性があるので 1,000,000,007 で割った余りを答えよ.

入力形式

最初の行に HW がスペース区切りで与えられる.

次の H 行には、チェス盤のマス目に書かれている数値として W 個の 012 のいずれかの整数がスペース区切りで与えられる.

出力形式

良いナイトの配置の数を 1,000,000,007 で割った余りを出力せよ.

制約

  • 1 ≤ H ≤ 50
  • 1 ≤ W ≤ 16

入出力例

入力例 1

5 5
0 2 0 2 0
2 0 0 0 2
0 0 0 0 0
2 0 0 0 2
0 2 0 2 0

出力例 1

5

入力例 2

3 3
2 2 2
2 0 2
2 2 2

出力例 2

8

入力例 3

7 7
2 2 2 2 2 2 2
2 1 1 2 1 1 2
2 0 1 0 1 0 2
2 2 0 2 0 2 2
2 0 1 0 1 0 2
2 1 1 2 1 1 2
2 2 2 2 2 2 2

出力例 3

96

入力例 4

7 3
2 2 2
1 0 1
0 1 0
1 1 1
0 1 0
1 0 1
2 2 2

出力例 4

8

入力例 5

6 6
0 2 0 1 0 2
2 0 1 2 2 2
0 2 2 0 0 0
2 0 2 0 2 0
0 2 2 1 0 2
0 0 0 2 0 2

出力例 5


1

入力例 6

16 16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 6

1

謝辞

この問題は Tester と Writer がアジア地区予選の問題に関して話し合ったのをきっかけとして作られた。
Source: Kyoto University Programming Contest 2011 , Kyoto, Japan, 2011-08-06
Problem Setter:  Shingo Mori ,  Tester: Yasuharu Hirasawa
http://www.kupc.jp/2011.html