Prize Game

Time Limit : 2 sec, Memory Limit : 65536 KB

Problem F: Prize Game

Problem

新しいゲームセンターが開店することになった。たくさんのお客さんを取り入れるために、全く新しいプライズゲームを設置することになった。

このプライズゲームはR×Cのグリッドから構成される。各マスは空白か、1〜18のいずれかの数字が書かれている。プレイヤーはひとつの空白のマスを選択し、そのマスの景品を獲得できる。ただし、マスにある景品はプレイヤーから見ることができない。

スタッフはこのプライズゲームに景品を設置しなければならない。スタッフは以下のルールが守られていれば、どのように景品を配置してもよい。数字が書かれているマスについて、その数字をxとすると、その数字を中心とする凸型の範囲の中に景品がちょうどx個置かれている必要がある(下の図を参照)。この凸型の出っ張っている部分は上を向いている。また、景品は空白のマスのみに置くことができ、1つのマスに3個まで置くことが出来る。1個も置かないことも可能である。

凸型の範囲の図
中央の数字が5だった場合の景品の置き方の例。オレンジ色の部分にちょうど計5個の景品が置かれている必要がある。

お客さんに景品の場所が簡単に推測されては大損である。そこで、オープニングスタッフであるあなたに、上記ルールに則った景品の置き方の場合の数を数えてもらいたい。ただし、景品は互いに区別できないものとする。答えは大きくなる場合があるので答えの場合の数を1000000007で割った余りを答えなさい。

Input

R C
a1,1 a1,2 ... a1,C
a2,1 a2,2 ... a2,C
:
aR,1 aR,2 ... aR,C

1行目に2つの整数R,Cが空白区切りで与えられる。それぞれグリッドの行数と列数を表す。次にプライズゲームを表すグリッドの情報がR行で与えられる。グリッドの情報のi行目にはC個の整数 ai,jが空白区切りで与えられる。ai,jはグリッドのij列のマス情報を表す。0の場合は空白のマス、それ以外の場合は数字ai,jが書かれたマスを表す。また、与えられるグリッドは1行目がプライズゲームの一番上を表し、R行目が一番下を表す。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ R,C ≤ 6
  • 0 ≤ ai,j ≤ 18 (1 ≤ iR , 1 ≤ jC)

Output

ルールに則った景品の置き方の場合の数を1000000007で割った余りを1行に出力せよ。

Sample Input 1

3 3
0 0 0
0 18 0
0 0 0

Sample Output 1

16

Sample Input 2

3 3
0 0 0
0 2 0
0 0 0

Sample Output 2

336

Sample Input 3

3 3
0 1 0
1 0 0
0 1 1

Sample Output 3

1

Sample Input 4

1 1
1

Sample Output 4

0

Sample Input 5

6 6
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

Sample Output 5

80065005

Source: University of Aizu Programming Contest 2013 , Aizu Commpetitive Programming Camp 2013 Day 2, Japan, 2013-09-04