1206 - Linear Algebra

Time Limit: 2s Memory Limit: 128MB

Submissions: 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
杨少侠