Tr A

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<cstdlib>#include<queue>#include<set>#include<vector>using namespace std;#define M 9973int T,n,k;struct matri{      int f[10][10];};matri mul(matri a,matri b){     matri c;     memset(c.f,0,sizeof(c.f));     for(int k=0;k<n;k++)            for(int i=0;i<n;i++)            {                if(!a.f[i][k]) continue;                for(int j=0;j<n;j++)                {                   if(!b.f[k][j]) continue;                   c.f[i][j]=(c.f[i][j]+a.f[i][k]*b.f[k][j])%M;                }            }      return c;}matri pow_(matri a,int b){     matri s;     memset(s.f,0,sizeof(s.f));     for(int i=0;i<n;i++)            s.f[i][i]=1;     while(b)     {         if(b&1)            s=mul(s,a);         a=mul(a,a);         b=b>>1;     }     return s;}int main(){     scanf("%d",&T);     while(T--)     {        matri e;        scanf("%d%d",&n,&k);        for(int i=0;i<n;i++)            for(int j=0;j<n;j++)                  scanf("%d",&e.f[i][j]);        e=pow_(e,k);        int ans=0;        for(int i=0;i<n;i++)            ans=(ans+e.f[i][i])%M;        printf("%d\n",ans);     }     return 0;}