# def climbStairs(n: int) -> int:
#     if n < 1 or n > 45:
#         return 0
#     else:
#         a = 1
#         b = 1
#         for i in range(2, n + 1):
#             a, b = b, a + b
#         return b

# print(climbStairs(4))

def f(n):
    cach = {}
    def g(n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        else:
            if g(n - 1) in cach[n - 1]:
                return cach[n - 1] + g(n)
            else: