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

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:
        S = pow0111(n // 2)
        S2 = matsquare(S)
        return S2  if n % 2 == 0   else matmul0111(S2)

def fib8(i):
    M = pow0111(i)
    return M[1]