n = int(input())
# 动规解法
if n < 3:
    print(n)
else:    
    dp = [0] * (n+1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-2] + dp[i-1]
    print(dp[n])

# 循环相加解法
if n < 3:
    print(n)
else:
    k1, k2 = 1, 2
    i = 3
    while i <= n:
        k = k1 + k2
        k1, k2 = k2, k
        i += 1
    print(k)

# 递归解法  
def func(n:int):
    if n < 3:
        return n
    else:
        return (func(n - 1) + func(n - 2))
print(func(n))