It is November 18 now in Japan. By the way, 11 and 18 are adjacent Lucas numbers.  You are given an integer N. Find the N-th Lucas number.  Here, the i-th Lucas number L_i is defined as follows:    * L_0=2   * L_1=1   * L_i=L_{i-1}+L_{i-2} (i≥2)
x = input()
x = int(x)

answer = []
for p in range(2, 10):

    for i in range(1, 32):
        if i**p > x:
            answer.append((i-1)**p)
            break
        elif pow(i, p) == x:
            answer.append(i**p)
            break

print(answer)
print(max(answer))
N = int(input())

L = []
L.append(2)
L.append(1)
if N == 1:
    print(L[1])
else:
    for i in range(2, N+1):
        L.append(L[i-1] + L[i-2])
    print(L[N])