1206  Linear Algebra
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 69
Solved: 43
 Description
 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.
 sample input

2 4 5 3 4 5 3 4 5 6 2 1 3 4 1 3 3 3 3 2 1000 1 2 4 5
 sample output

79689 31068
 hint
 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.
 source
 杨少侠