r × c のグリッドが与えられる。
グリッドのいくつかのマスには1から8までの数字が書かれている。
数字が書かれているマスと他の数字が書かれているマスを線で結ぶ必要がある。
数字が書かれているマスについて、そのマスに書かれている本数だけ、他のマスとの間に線を結ぶ必要がある。
ただし、線を結べるのは上下左右方向だけで、一つの方向について、最大2本までである。
他の数字を跨いで線で結ぶことはできない。
また、次のように交差してしまう結び方をすることはできない。
グリッドが入力として与えられるので、数字が書かれているマス全てを正しく結ぶ方法が、何通りあるのかを数えて欲しい。
入力は以下のフォーマットで与えられる。
r c grid1 . . . gridr-1
gridi は長さcの文字列で、1から8までの数字か"."からなる。
入力は以下の制約を満たす
1 ≤ r,c ≤ 10
答えの値を100,000,007で割った余りを1行に出力せよ
3 3 .1. 1.1 .1.
0
1 3 1.1
1
3 3 4.2 ... 2..
1
7 7 2.3.1.1 ....... 2...... ....... ..3.3.. ....... 2.2.4.3
10