multiplies two square matrices mata and matb of size n x n time complexity on3 returns the identity matrix of size n x n time complexity on2 calculates matn by repeated squaring time complexity od3 logn d dimension of the square matrix mat n power the matrix is raised to multiplies two square matrices mata and matb of size n x n time complexity o n 3 returns the identity matrix of size n x n time complexity o n 2 calculates mat n by repeated squaring time complexity o d 3 log n d dimension of the square matrix mat n power the matrix is raised to
def multiply(matA: list, matB: list) -> list:
    
    n = len(matA)
    matC = [[0 for i in range(n)] for j in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                matC[i][j] += matA[i][k] * matB[k][j]

    return matC


def identity(n: int) -> list:
    
    I = [[0 for i in range(n)] for j in range(n)]

    for i in range(n):
        I[i][i] = 1

    return I


def matrix_exponentiation(mat: list, n: int) -> list:
    
    if n == 0:
        return identity(len(mat))
    elif n % 2 == 1:
        return multiply(matrix_exponentiation(mat, n - 1), mat)
    else:
        tmp = matrix_exponentiation(mat, n // 2)
        return multiply(tmp, tmp)