def dot(p,q):
    """Dot-product of two vectors (represented as equal-length lists).
    """
    return sum((i*j for i,j in zip(p,q)), 0)

def matmul(L, R):
    """Multiply two matrices (represented as lists-of-rows).
    >>> matmul([[2]], [[3]])
    [[6]]
    >>> matmul([[1,1],[1,0]], [[0,1],[1,-1]])
    [[1, 0], [0, 1]]
    """
    return [[dot(Lrow, Rcol) for Rcol in zip(*R)] for Lrow in L]

def fib(n):
    """Calculate the nth Fibonacci number, indexed as f(0)=1, f(1)=0, f(2)=1.
    >>> [fib(n) for n in range(18)]
    [1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
    """
    result = [[1, 0], [0, 1]]
    a, b, c = 1, 1, 0
    while n:
        n, d = divmod(n, 3)
        if d == 0:
            pass
        elif d == 1:
            result = matmul(result, [[a,b],[b,c]])
        elif d == 2:
            n += 1
            d = -1
            result = matmul(result, [[-c,b],[b,-a]])
        abc, ab2, cb2 = b*(a+c),  a**2 + b**2,  c**2 + b**2
        a, b, c = b * abc + a * ab2,  a * abc + b * cb2,  b * abc + c * cb2
    return result[1][1]