fast fibonacci modulo numbers

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

void mdot(long long **a, long long **b, long long**c, long long k, long long p) {
    for(int i = 0; i < k; i++){
        for(int j = 0; j < k; j++){
            c[i][j] = 0;
        }
    }
    for(int i = 0; i < k; i++){
        for(int j = 0; j < k; j++){
            for(int z = 0; z < k; z++){
                c[i][j] += (a[i][z]*b[z][j])%p;
            }
        }
    }
}

void mpow(long long **a, long n, long long k, long long p, long long** b) {
    if(n == 0){
        for(int i = 0; i < k; i++){
            for(int j = 0; j < k; j++){
                if(i == j) b[i][j] = 1;
                else b[i][j] = 0;
            }
        }
    }
    if(n == 1){
        for(int i = 0; i < k; i++){
            for(int j = 0; j < k; j++){
                b[i][j] = a[i][j];
            }
        }
    }else if(n%2 == 0){
        long long** z = malloc(k*sizeof(long long*));
        for(int i = 0; i < k; i++){
            z[i] = malloc(k*sizeof(long long));
        }
        mpow(a, n/2, k, p, z);
        mdot(z, z, b, k, p);
        for(int i = 0; i < k; i++){
            free(z[i]);
        }
        free(z);
    }else{
        long long** z = malloc(k*sizeof(long long*));
        for(int i = 0; i < k; i++){
            z[i] = malloc(k*sizeof(long long));
        }
        mpow(a, n-1, k, p, z);
        mdot(z, a, b, k, p);
        for(int i = 0; i < k; i++){
            free(z[i]);
        }
        free(z);
    }
}

int main(void) {
    long long k;
    long long N;
    long long p;
    long long *F, **A;
    scanf("%lld%lld%lld", &k, &N, &p);
    F = malloc(k*sizeof(long long));
    A = malloc(k*sizeof(long long *));
    for (int i = 0; i < k; i++) {
        scanf("%lld", &F[i]);
        F[i] %= p;
    }
    for (int i = 0; i < k; i++) {
        A[i] = malloc(k*sizeof(long long));
        scanf("%lld", &A[0][i]);
        A[0][i] %= p;
    }

    if (N <= k) {
        printf("%lld", F[N-1]);
        free(F);
        for(int i = 0; i < k; i++){
            free(A[i]);
        }
        free(A);
        return 0;
    }
    N -= k;

    for (int i = 1; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (i - 1 == j) A[i][j] = 1;
            else A[i][j] = 0;
        }
    }
    long long** b = malloc(k*sizeof(long long*));
    for(int i = 0; i < k; i++){
        b[i] = malloc(k*sizeof(long long));
    }
    mpow(A, N, k, p, b);
    for(int i = 0; i < k; i++){
        free(A[i]);
    }
    free(A);
//    for (int i = 0; i < k; i++) {
//        for (int j = 0; j < k; j++) {
//            printf("%u ", b[i][j]);
//        }
//        printf("\n");
//    }
    long long variable = 0;
    for (int i = 0; i < k; i++){
        variable += b[0][i]*F[k-1-i];
    }
    printf("%lld", variable%p);
    free(F);
    for(int i = 0; i < k; i++){
        free(b[i]);
    }
    free(b);
}