#include <stdio.h>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;
__int64 n;
struct node
{
    __int64 a[15][15];
};
node mut_mut(node e,node d) //两个矩阵相乘
{ 
    __int64 i,j,k;
    node m;
    memset(m.a,0,sizeof(m.a));
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            for(k=1; k<=n; k++)
            {
                m.a[i][j]+=e.a[i][k]*d.a[k][j];
                m.a[i][j]%=9973;
            }
    return m;
}
node fastmi(node a1,__int64 cishu)  //快速幂 
{
    __int64 i;
    node f;
     memset(f.a,0,sizeof(f.a));
    for(i=1; i<=n; i++)
        f.a[i][i]=1;
    while(cishu)
    {
        if(cishu&1)
            f=mut_mut(f,a1);
        a1=mut_mut(a1,a1);
        cishu>>=1;
    }
    return f;
}
int main()
{
    __int64 i,j,t,cishu;
    node c,last;
    scanf("%I64d",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&n,&cishu);
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            {
                scanf("%I64d",&c.a[i][j]);
                c.a[i][j]%=9973;
            }
        last=fastmi(c,cishu);
        __int64 sum=0;
        for(i=1; i<=n; i++)
        {
            sum+=last.a[i][i];
            sum%=9973;
        }
        printf("%I64d\n",sum);
        memset(last.a,0,sizeof(last.a));
    }
    return 0;
}