def matmult(a, b):
    return (a[0] * b[0] + a[1] * b[2], a[0] * b[1] + a[1] * b[3], a[2] * b[0] + a[3] * b[2], a[2] * b[1] + a[3] * b[3])
    
def fib(n):
    a = (1,0,0,1)
    x = (1,1,1,0)
    while n > 0:
        if n & 1 == 1:
            a = matmult(a, x)
            
        n >>= 1    
        x = matmult(x, x)

    return a[0]
    
for i in xrange(100):
    print fib(i)
    
print fib(1000)
print fib(10000)
print fib(100000)