Problem Description

A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。

 

Input

数据的第一行是一个T，表示有T组数据。每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。

 

Output

对应每组数据，输出Tr(A^k)%9973。

 

 

 

Sample Input

22 21 00 13 999999991 2 34 5 67 8 9

 

 

 

Sample Output

2 2686

 

 

 

Author

xhd

 

 

Source

 

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 #define N 10 6 #define MOD 9973 7 int n,k; 8 struct Matrix 9 {10     int mp[N][N];11 }matrix;12 Matrix Mul(Matrix a,Matrix b)13 {14     Matrix res;15     int i,j,k;16     for(i=0;i
          
           >= 1;40     }41     return res;42 }43 int main()44 {45     int t;46     scanf("%d",&t);47     while(t--)48     {49         scanf("%d%d",&n,&k);50         for(int i=0;i