Matrix Quickpower Algorithm

namespace Matrix{
  #define mx ini.mat
  int n,k;
  struct ma{
    int mat[MAXN][MAXN];
    void init(){memset(mat,0,sizeof(mat));}
    void pt(int num){
      for (int i=0;i<=num;i++){
        for (int j=0;j<=num;j++){
          cout << mat[i][j] << " ";
        }
        cout << endl;
      }
      cout << endl;
    }
  }ini;
  inline ma mul(ma a, ma b){
    ma c;
    c.init();
    for (int k=1;k<=n;k++){
      for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
          c.mat[i][j] = (c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
        }
      }
    }
    return c;
  }
  inline ma qpow(ma m, int num){
    if (num==1) return m;
    if (num%2==1) return mul(qpow(m,num-1),m);
    ma tmp = qpow(m,num/2);
    return mul(tmp,tmp);
  }
  inline void solve();
  #undef mx
}