题意：非常清晰！

直接搞吧。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stack>

#include <queue>

#include <map>

#include <set>

#include <vector>

#include <math.h>

#include <algorithm>

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

const double pi = acos(-1.0);

const int mod =9973;

const int N = 20;

struct asd{

    LL a[N][N];

};

int n;

asd mul(asd a,asd b)

{

    asd ans;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=n;j++)

        {

            ans.a[i][j]=0;

            for(int k=1;k<=n;k++)

            {

                ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%mod;

            }

        }

    }

    return ans;

}

asd quickmul(asd z,int g)

{

    asd ans;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=n;j++)

        {

            if(i==j)

                ans.a[i][j]=1;

            else

                ans.a[i][j]=0;

        }

    }

    while(g)

    {

        if(g%2)

        {

            ans=mul(ans,z);

        }

        g/=2;

        z=mul(z,z);

    }

    return ans;

}

int main()

{

    int t;

    int i,j,k;

    asd s;

    scanf("%d",&t);

    while(t--)

    {

        asd A;

        scanf("%d%d",&n,&k);

        for(i=1;i<=n;i++)

        {

            for(j=1;j<=n;j++)

            {

                scanf("%lld",&A.a[i][j]);

            }

        }

        s=quickmul(A,k);

        LL ans=0;

        for(i=1;i<=n;i++)

        {

            ans+=s.a[i][i];

        }

        printf("%lld\n",ans%mod);

    }

    return 0;

}