http://acm.hdu.edu.cn/showproblem.php?pid=1575
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N=11,mod=9973;
int n,b;
struct Matrix
{
int m[N][N];
}curr;
Matrix multi(Matrix a,Matrix b)
{
Matrix ans;
memset(ans.m,0,sizeof(ans.m));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
}
}
}
return ans;
}
Matrix fast_pow(Matrix a,int b)
{
Matrix ans,base=a;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
ans.m[i][j]=(i==j);
}
}
while(b)
{
if(b&1)
{
ans=multi(ans,base);
}
base=multi(base,base);
b>>=1;
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&b);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&curr.m[i][j]);
}
}
curr=fast_pow(curr,b);
int ans=0;
for(int i=0;i<n;i++)
{
ans=(ans+curr.m[i][i])%mod;
}
printf("%d\n",ans%mod);
}
}
