from functools import lru_cache


@lru_cache
def fibonacci(n):
    return n if n <= 1 else fibonacci(n - 1) + fibonacci(n - 2)

def fibonacci(n):
    if n < 0:
        return -1
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    first = 0
    second = 1
    for _ in range(n - 1):
        first, second = second, first + second

    return second