identity_matrix = [[1,0],[0,1]]
x = [[0,1],[1,1]]

def matrix_multiply(a, b):
    return [[a[0][0]*b[0][0] + a[0][1]*b[1][0],
             a[0][0]*b[0][1] + a[0][1]*b[1][1]],
            [a[1][0]*b[0][0] + a[1][1]*b[1][0],
             a[1][0]*b[0][1] + a[1][1]*b[1][1]]]
    
def matrix_power(m, n):
    result = identity_matrix
    power = m
    while n > 0:
        if n % 2 == 1:
            result = matrix_multiply(result, power)
        power = matrix_multiply(power, power)
        n = n //2
    return result
    
    
def fib (n) :
    return matrix_power(x, n)[0][1] 
    
print ([fib(i) for i in range(40)])

print ([matrix_power(x, n) for n in range(6)])