import sys
import timeit
from functools import lru_cache

index = {0: 0, 1: 1, 2: 1}


def routine(i: int):
    try:
        return index[i]
    except KeyError:
        fib_i = fibonacci(i)
        index[i] = fib_i
        return fib_i


@lru_cache(maxsize=None)
def fibonacci(n: int) -> int:

    if n in index:
        return index[n]

    k = int(n / 2)

    return routine(k + 1) * routine(n - k) + routine(k) * routine(n - k - 1)


sys.setrecursionlimit(100)
print(timeit.timeit('fibonacci(1000000)', setup="from __main__ import fibonacci", number=1000))