Fibonacci with Memoisation

Lab Python Intermediate 20 points

Print the n-th Fibonacci number (F0 = 0, F1 = 1) using recursion with functools.lru_cache.

Input

One integer 0–90.

Output

F(n)

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

Plain recursive Fibonacci recomputes the same values exponentially many times.

@lru_cache remembers results.

Solution explanation

Memoisation turns exponential time into linear time by caching each fib(k).

Show solution

from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


print(fib(int(input())))

Output

Answer