#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <queue>#include <cmath>#include <stack>#include <map>#pragma comment(linker, "/STACK:1024000000")#define EPS (1e-8)#define LL long long#define ULL unsigned long long#define INF 0x3f3f3f3fusing namespace std;const int MAXN = 61;struct MAT{int row,col;int mat[MAXN][MAXN];void Init(int R,int C,int val){row = R,col = C;for(int i = 1;i <= row; ++i)for(int j = 1;j <= col; ++j)mat[i][j] = (i == j ? val : 0);}MAT Multi(MAT c,int MOD){MAT tmp;tmp.Init(this->row,c.col,0);int i,j,k;for(i = 1;i <= tmp.row; ++i)for(j = 1;j <= tmp.col; ++j)for(k = 1;k <= this->col; ++k)(tmp.mat[i][j] += this->mat[i][k]*c.mat[k][j]) %= MOD;return tmp;}MAT Quick(int n,int MOD){MAT res,tmp = *this;res.Init(row,col,1);while(n){if(n&1)res = res.Multi(tmp,MOD);tmp = tmp.Multi(tmp,MOD);n >>= 1;}return res;}void Output(){cout<<"****************"<<endl;int i,j;for(i = 1;i <= row; ++i){for(j = 1;j <= col; ++j)printf("%3d ",mat[i][j]);puts("");}cout<<"&&&&&&&&&&&&&"<<endl;}};int main(){freopen("data1.in","r",stdin);int T;scanf("%d",&T);MAT A;int n,m,i,j,sum;while(T–){scanf("%d %d",&n,&m);A.Init(n,n,0);for(i = 1;i <= n; ++i)for(j = 1;j <= n; ++j)scanf("%d",&A.mat[i][j]);A = A.Quick(m,9973);for(sum = 0 ,i = 1;i <= n; ++i)(sum += A.mat[i][i] ) %= 9973;printf("%d\n",sum);}return 0;}
，深重如溺入蓝色的海洋，无法呼吸。
