Time Limit: 1000 ms
Memory Limit: 65535 ms
calculate a matrix A which is obtained when adding matrix B^n recursively to unit matrix I, ie, I+B+B^2+B^3+...B^n.Notice that B is a formal matrix whose number of rows and columns are equal.
The first line contains an integer t ( 1 <= t <= 10 ): the number of test cases. Then for each test case:The first line contains two integers n,k ( 1 <= n<= 10^8 ,2 <= k <= 20 ),where k is the size of matrix B.
For each test case, output the result in the form of sample.You should print the case number and matrix A.Each element of matrix should be mod 10007