# Takahashi's Fibonacci number algorithm
def fib(n):
    def aux(n):
        """Return F(n),L(n)"""
        if n == 0: return 0,2
        else:
            f,l = aux(n//2)
            temp = f*f
            f = (f+l)//2
            sign = 1-n//2%2*2
            f = 2*(f*f)-3*temp-2*sign
            l = 5*temp+2*sign
            if n%2 == 0: return f,l
            else: return (f+l)//2, (5*f+l)//2
    if n%2 == 0:
        f,l = aux(n//2)
        return f*l
    else:
        f,l = aux(n-1)
        return (f+l)//2

print(fib(10000))