Pattern

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Alice and Bob are playing a game. Alice takes a paper with $N \times M$ points arranging in $N$ rows and $M$ columns. First, Alice colors some points with one of $5$ colors: $c_0, c_1, c_2, c_3, c_4$. And then, Bob draws some lines between adjacent points which own a common edge. If the color of a point is $c_i$, Bob must draw exactly $i$ lines linking this point. Otherwise, Bob can draw any number of lines linking it. At last, Alice would color the rest points, with the same rules that the point which links $i$ lines should be painted the color $c_i$. After the game, Alice might get different patterns of the colors. Suppose the initial colored paper can lead to totally $K$ patterns, and there are $P_i$ ways for Bob to draw lines for the $i$-th patterns. Alice wants to know $\sum_{i=1}^K P_i^2$.

Input

The first line of input contains an integer t which is the number of test cases. Then t test cases follow.
For each test case, the first line consists of two integers N(N ≤ 66), and M(M ≤ 6). The i-th line of the next N lines contains M integers, and among them the j-th integer donates the point (i, j). If the point is panted color $c_i$ , the integer is i, otherwise it is -1.

Output

For each test cases, output $\sum_{i=1}^{K} P_i^2$ modulo 10007.

Sample Input

2 2 2 -1 -1 -1 -1 3 3 1 1 1 1 0 1 1 1 1

Sample Output

18 4
Hint

Hint

jiangzijing2015

Source

2016ACM/ICPC亚洲区青岛站-重现赛(感谢中国石油大学)

提交代码