import sys
input = sys.stdin.readline

def basic_step_ptn_nums(x): # 'x'段までのパターン総数
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        dp[:2] = 1, 1 # 固定部分
        for i in range(2, x+1):
            dp[i] = dp[i-1] + dp[i-2] # -1段目と-2段目の合計
        print(dp[-1])

basic_step_ptn_nums(8)
