#include"bits/stdc++.h"
using namespace std;
const int mod = 9973;
int n, k;
struct Mat {
int mat[11][11];
Mat() {
memset(mat, 0, sizeof(mat));
}
friend Mat operator * (Mat a, Mat b) {
Mat c;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % mod;
return c;
}
};
Mat Mat_pow(Mat m, int k) {
Mat ans;
for(int i = 1; i <= n; i++)
ans.mat[i][i] = 1;
while(k) {
if(k & 1)
ans = ans * m;
m = m * m;
k >>= 1;
}
return ans;
}
int main() {
int T; Mat m;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &m.mat[i][j]);
m = Mat_pow(m, k);
int ans = 0;
for(int i = 1; i <= n; i++)
ans += m.mat[i][i];
printf("%d
", ans % mod);
}
return 0;
}