def matsquare(M):
    # Compute M*M
    a, b, c = M

def matmul0111(M):
    # Compute M * (0,1,1,1)
    a, b, c = M
    return (b, a+b, b+c)

def pow0111(n):
    if n == 0:
        return (1, 0, 1)
    else:
        a, b, c = pow0111(n // 2)
        a, b, c, = a*a+b*b, b*(a+c), b*b+c*c
        if n % 2 == 1:
            a, b, c = b, a+b, b+c
        return a, b, c

def fib9(i, a, b, c):
    a,b,c = pow0111(i)
    return b

if __name__ == '__main__':
    for i in range(13):
        print(i, fib9(i,1,0,1))

# 1 1 2 3 5
# 8 13 21 34 55
# 89 144