#include<iostream>
using namespace std;
class matrix
{
public:
int m[12][12];
int o[12][12];
int f[12][12];
int n,cnt;
public:
void work(int c);
void findans();
void init();
};
void matrix::init(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&m[i][j]);
o[i][j] = m[i][j];
}
}
void matrix::work(int c){
int i,j,k;
if(c==1)
return;
if(c==2)
{
memset(f,0,sizeof(f));
for(i = 1;i<=n;i++)
for(j = 1;j<=n;j++)
for(k = 1;k<=n;k++)
f[i][j] = (f[i][j]+m[i][k]*m[k][j])%9973;
for(i = 1;i<=n;i++)
for(j=1;j<=n;j++)
m[i][j] = f[i][j];
return ;
}
if(c&1)
{
work(c/2);
memset(f,0,sizeof(f));
for(i = 1;i<=n;i++)
for(j = 1;j<=n;j++)
for(k = 1;k<=n;k++)
f[i][j] = (f[i][j]+m[i][k]*m[k][j])%9973;
for(i = 1;i<=n;i++)
for(j=1;j<=n;j++)
m[i][j] = f[i][j];
memset(f,0,sizeof(f));
for(i = 1;i<=n;i++)
for(j = 1;j<=n;j++)
for(k = 1;k<=n;k++)
f[i][j] = (f[i][j]+m[i][k]*o[k][j])%9973;
for(i = 1;i<=n;i++)
for(j=1;j<=n;j++)
m[i][j] = f[i][j];
}
else
{
work(c/2);
memset(f,0,sizeof(f));
for(i = 1;i<=n;i++)
for(j = 1;j<=n;j++)
for(k = 1;k<=n;k++)
f[i][j] = (f[i][j]+m[i][k]*m[k][j])%9973;
for(i = 1;i<=n;i++)
for(j=1;j<=n;j++)
m[i][j] = f[i][j];
}
}
void matrix::findans(){
int sum = 0;
for(int i=1;i<=n;i++)
sum = (sum+m[i][i])%9973;
cout<<sum<<endl;
}
int main()
{
int T;
matrix a;
cin>>T;
while(T--)
{
int nn,i,j;
cin>>a.n>>a.cnt;
a.init();
a.work(a.cnt);
a.findans();
}
return 0;
}