from time import time

treden = int(input("Hoeveel treden telt je trap: "))

memo = [0, 1, 2]

# programmeer hieronder de oplossing

for trap in range(3, treden + 1):
    aantal_combinaties = memo[trap-1] + memo[trap-2]
    memo.append(aantal_combinaties)
    

# start = time()
print(f"Er zijn {memo[treden]} mogelijke manieren om de trap de beklimmen.")
# print(f'{time() - start:.12f}')