Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10⁹) and m (m < 10⁴). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output the elements of S modulo m in the same way as A is given.

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int maxn=;

 int mod,n,K;

 struct Matrix{

     int mat[maxn][maxn];

     Matrix(){

         memset(mat,,sizeof(mat));

     }

     Matrix operator +(Matrix a){

         Matrix r;

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

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

                 (r.mat[i][j]=(mat[i][j]+a.mat[i][j])%mod)%=mod;

         return r;

     }

     Matrix operator *(Matrix a){

         Matrix r;

         for(int i=,s;i<=n;i++)

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

                 s=mat[i][k];

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

                     (r.mat[i][j]+=(s*a.mat[k][j])%mod)%=mod;

             }

         return r;

     }

     Matrix operator ^(int k){

         Matrix r,x;

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

             r.mat[i][i]=;

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

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

                 x.mat[i][j]=mat[i][j];

         while(k){

             if(k&)

                 r=r*x;

             k>>=;

             x=x*x;

         }

         return r;

     }

 }A,B,ans;

 Matrix Solve(int k){

     if(k==)return A;

     if(k%)return A+A*Solve(k-);

     else return ((A^(k/))+B)*Solve(k/);

 }

 int main(){

 #ifndef ONLINE_JUDGE

     //freopen("","r",stdin);

     //freopen("","w",stdout);

 #endif

     scanf("%d%d%d",&n,&K,&mod);

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

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

             scanf("%d",&A.mat[i][j]);

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

         B.mat[i][i]=;

     ans=Solve(K);

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

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

             printf("%d ",ans.mat[i][j]);

         printf("\n");

     }

     return ;

 }