import sys
from functools import lru_cache
n = int(input())

@lru_cache
def get_n(n):
    if n == 1 or n == 2:
        return 1
    return get_n(n-1)+get_n(n-2)

print(get_n(n))

斐波那契数列

1 1 2 3 5 8 f(n-1) + f(n-2)