def matrix_mul(A, B):
    ROWS_A, COLS_A = len(A), len(A[0])
    ROWS_B, COLS_B = len(B), len(B[0])
    assert COLS_A == ROWS_B
    COMMON_D = ROWS_B

    # zeros for Rows-A x Cols-B
    M_TIMES = []
    for r in range(ROWS_A):
        M_TIMES.append( [0] * COLS_B )

    # Loop over Rows-A, then Cols-B, then the common dimension
    for rA in range(ROWS_A):
        for cB in range(COLS_B):
            for t in range(COMMON_D):
                M_TIMES[rA][cB] += A[rA][t]*B[t][cB]
    return M_TIMES
    
def print_matrix(M, skip_indexes=[]):
    ROWS, COLS = len(M), len(M[0])
    for r in range(ROWS):
        for c in range(COLS):
            if skip_indexes[r][c]:
                continue
            print(M[r][c])
            
#####
A = [[1,1,0],[0,1,0],[0,0,1]]
B = A
EXP=100
for _ in range(EXP-1):
    B = matrix_mul(B, A)
# print(B)
print_matrix(B, skip_indexes=[[False, False,True],[True, False, True],[True, False, False]])

if __name__ == "__main__":
  n: int = 100; # 100th power
  print(*[1, 1*n, 1, 0, 1], sep = '\n')

import math
A = [[1,math.pow(100,1/100),1,0,1]]


for i in A:
    for q in i:
        print(math.floor(q**100))

def matrixPower(A, k):
    row, col = len(A), len(A[0])
    if k == 1:
        # base
        return A
    elif (k > 1):
        # recursive
        A_less_1 = matrixPower(A,k-1)
        last_A = A
        B = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
        
        for i in range(len(A_less_1)):
            for j in range(len(A_less_1[0])):
                for k in range(len(last_A)):
                    B[i][j] += A_less_1[i][k] * last_A[k][j]
        return B            
    
if __name__ == "__main__":
    A = [[1, 1, 0], [0, 1, 0], [0, 0, 1]]
    Apow100 = matrixPower(A, 100)
    A1, A2, A3 = Apow100
    A, B, Z = A1
    Z, C, Z = A2
    Z, D, E = A3
    print(A, B, C, D, E, sep='\n')