#include<iostream>

#include<cstdio>

#include<cstring>

#define mod 9973

#define maxn 12

using namespace std;

struct mat{

    int s[maxn][maxn],n;

    mat (int n1){//构造器

        n = n1;

        memset(s,,sizeof(s));//一定要初始化

    }

    void init(){

        for(int i=;i<=n;i++){//单位矩阵的初始化，切记！

            s[i][i] = ;//如果没有这个的话就不能直接相乘

        }

    }

    mat operator * (const mat m){

        mat ans(this->n);//理解this的用法

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

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

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

                    ans.s[i][j] = (ans.s[i][j] + this->s[i][k] * m.s[k][j])%mod;

                }

            }

        }

        return ans;

    }

};

mat quick_mod(mat &m,int p){//和整数快速幂一样的方法，只不过这里面的乘是矩阵的相乘

    mat ans(m.n);

    ans.init();// ans一定要为单位矩阵的！

    while(p){

        if(p&){

            ans = ans * m;

        }

        m = m*m;

        p >>= ;

    }

    return ans;

}

int main()

{

    int t,n,k;

    cin >> t;

    while(t--){

        cin >> n >> k;

        mat m(n);

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

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

                cin >> m.s[i][j];

            }

        }

        mat ans(n);

        ans = quick_mod(m,k);

        int sum = ;

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

            sum = (sum+ans.s[i][i])%mod;

        }

        cout << sum << endl;

    }

    return ;

}