Most of the students of Grade 2008 have nearly or just finished Linear Algebra classes.Now give you a easy problem in Linear Algebra,now you can use your computer tool to pass it.
Give you a matrix,its size is N*N(N rows & N columns),and each number in it is less than 10.Then you need to do is just calculate the matrix^k(the value of k same matrices' multiplication).
Input
First Line:There is a number CAS(1<=CAS<=1000) means the number of cases you need to fill
Second Line~End -> all the cases
The format of each case:
First Line: two Numbers N,k(1<=N<=10&&1<=k<=1000000000)
2~N+1 Lines: Each Line have M numbers,meaning each row of the matrix.
Output
For each test case,calculate the answer matrix,each number in the matrix should module by 10007.
Just print the sum of the numbers in the matrix.
For the first sample case,you got the 4*4 matrix mat,a new matrix mat1=mat*mat*mat*mat*mat:
mat1 =
84412 123771 151468 65350
96834 142007 173792 74956
49448 72532 88772 38268
69342 101652 124392 53694
then module each elements by 10007
mat2 =
4356 3687 1363 5308
6771 1909 3673 4907
9420 2483 8716 8247
9300 1582 4308 3659
Then you sum all the elements ,The answer you get is 79689.