struct matrix{

 int a[N][N];

 void clear(){memset(a,0,sizeof a);}

 void operator *= (const matrix &x){

 static ll ans[N][N]={0};

 for (int i=0;i<N;i++)

 for (int k=0;k<N;k++) if (a[i][k])

 for (int j=0;j<N;j++)

 ans[i][j]+=a[i][k]*x.a[k][j];

 for (int i=0;i<N;i++)

 for (int j=0;j<N;j++)

 a[i][j]=ans[i][j]%10000,ans[i][j]=0;

 }

};