24829번 - Counting Codes 다국어

문제

You're one of the king's spies sent on a secret mission to retrieve an item of incredible value, an ancient scroll from the throne room. Legend has it, the scroll contains the answer to the $P$ versus $NP$ problem. When you finally reach the throne room, you realize there is a code the guards enter every day while observing them. As a spy, you've started to notice a few rules for each guard's code:

1. each code is a matrix consisting of nonzero decimal digits (integers from 1ドル$ to 9ドル$) with $m$ rows and $n$ columns
2. no digit repeats within any row of the code
3. for each digit $l$ in the code, except for those in the topmost row and rightmost column, let $u$ be the digit above it and let $r$ be the digit to its right in the code matrix. Then one of the following must be true:
   • $u$ is the product of $l$ and $r$
   • $u$ is the sum of $l$ and $r$
   • $u$ is the difference of $l$ and $r$ or $r$ and $l$
   • $u$ is the quotient of $l$ and $r$ or $r$ and $l$

On day 999ドル,ドル you've noticed a guard has seem to walked off while entering his code. Some digits have been omitted, but after careful consideration you think you can crack the code. Digits that have been omitted are represented with a 0ドル$. How many complete codes are possible, given the guard's partial code?

입력

A test case starts with a line containing two numbers $m$ (3ドル \le m \le 6$) and $n$ (3ドル \le n \le 6$), which is the number of rows and number of columns of the grid. The following $m$ lines contain $n$ integers from 0ドル$ to 9ドル,ドル separated by spaces. 0ドル$ indicates an unknown value that you can supply, and there will be at most $\lfloor \frac{m*n}{2} \rfloor$ unknown values.

You can assume the guard has followed the rules with the partial code (i.e. no repeated digits appear in any row in the input, and any three pairs of non-zero digits that form an L have the property described above).

출력

For each test case, print the number of complete codes you can find.

제한

힌트