新しいゲームセンターが開店することになった。たくさんのお客さんを取り入れるために、全く新しいプライズゲームを設置することになった。
このプライズゲームはR×Cのグリッドから構成される。各マスは空白か、1〜18のいずれかの数字が書かれている。プレイヤーはひとつの空白のマスを選択し、そのマスの景品を獲得できる。ただし、マスにある景品はプレイヤーから見ることができない。
スタッフはこのプライズゲームに景品を設置しなければならない。スタッフは以下のルールが守られていれば、どのように景品を配置してもよい。数字が書かれているマスについて、その数字をxとすると、その数字を中心とする凸型の範囲の中に景品がちょうどx個置かれている必要がある(下の図を参照)。この凸型の出っ張っている部分は上を向いている。また、景品は空白のマスのみに置くことができ、1つのマスに3個まで置くことが出来る。1個も置かないことも可能である。
中央の数字が5だった場合の景品の置き方の例。オレンジ色の部分にちょうど計5個の景品が置かれている必要がある。
お客さんに景品の場所が簡単に推測されては大損である。そこで、オープニングスタッフであるあなたに、上記ルールに則った景品の置き方の場合の数を数えてもらいたい。ただし、景品は互いに区別できないものとする。答えは大きくなる場合があるので答えの場合の数を1000000007で割った余りを答えなさい。
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はグリッドのi行j列のマス情報を表す。0の場合は空白のマス、それ以外の場合は数字ai,jが書かれたマスを表す。また、与えられるグリッドは1行目がプライズゲームの一番上を表し、R行目が一番下を表す。
入力は以下の条件を満たす。
ルールに則った景品の置き方の場合の数を1000000007で割った余りを1行に出力せよ。
3 3 0 0 0 0 18 0 0 0 0
16
3 3 0 0 0 0 2 0 0 0 0
336
3 3 0 1 0 1 0 0 0 1 1
1
1 1 1
0
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
80065005