|
||||||||||
PatternTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 265 Accepted Submission(s): 43 Problem 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
Sample Output
Hint Source | ||||||||||
|