#include <stdio.h>
#include <stdlib.h>

int** alloc(int n, int m) {
  int **A;
  A = (int**)malloc(sizeof(int*) * n);
  int i;
  for (i = 0; i < n; i++) {
    A[i] = (int*)malloc(sizeof(int) * m);
  }
  return A;
}

void dealloc(int n, int m, int** A) {
  int i;
  for (i = 0; i < n; i++)
    free(A[i]);
  free(A);
}

void print(int n, int m, int** A) {
  int i, j;
  for (i = 0; i < n; i++) {
    for (j = 0; j < m; j++)
      printf("%d ", A[i][j]);
    printf("\n");
  }
}

void mult(int n, int m, int p, int** A, int** B, int** C) {
  // A[n][m]
  // B[m][p]
  // C[n][p]
  int i, j, k;
  for (i = 0; i < n; i++) {
    for (j = 0; j < p; j++) {
      C[i][j] = 0;
      for (k = 0; k < m; k++) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
}

void id(int n, int** I) {
  int i, j;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++)
      I[i][j] = 0;
    I[i][i] = 1;
  }
}

copy(int n, int m, int** A, int**B) {
  int i, j;
  for (i = 0; i < n; i++)
    for (j = 0; j < m; j++)
      A[i][j] = B[i][j];
}

void pow(int n, int** A, int exp, int** B) {
  int** C = alloc(n, n);
  id(n, B);
  id(n, C);
  while (exp > 0) {
    if (exp & 1) {
      mult(n, n, n, B, A, C);
      copy(n, n, B, C);
    }
    mult(n, n, n, A, A, C);
    copy(n, n, A, C);
    exp /= 2;
  }
  dealloc(n, n, C);
}

int main() {
  return 0;
}