Problem:
 Score : 200 points    Problem Statement 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)       Constraints  1≤N≤86  It is guaranteed that the answer is less than 10^{18} .  N is an integer.         Input Input is given from Standard Input in the following format:  N       Output Print the N -th Lucas number.        Sample Input 1 5      Sample Output 1 11   L_0=2  L_1=1  L_2=L_0+L_1=3  L_3=L_1+L_2=4  L_4=L_2+L_3=7  L_5=L_3+L_4=11   Thus, the 5 -th Lucas number is 11 .       Sample Input 2 86      Sample Output 2 939587134549734843

Solution (Python):
N = int(input())
L = [0]*(N+1)
L[0] = 2
L[1] = 1
for i in range(2,N+1):
    L[i] = L[i-1] + L[i-2]
print(L[N])

Solution (Python):
N = int(input())
luka = [2, 1]
for i in range(0, N):
    next = luka[i] + luka[i+1]
    luka.append(next)
print(luka[N])

Solution (Python):
N = int(input())
Li_2 = 2
Li_1 = 1
Li = 0
if N > 1:
    for i in range(2, N+1):
        Li = Li_1 + Li_2
        Li_2 = Li_1
        Li_1 = Li
print(Li) if N !=1 else print(Li_1)

Solution (Python):
N = int(input())
pre2,pre1 = 2,1
if N == 1:print(1)
else:
    for i in range(2,N+1):
        l = pre2 + pre1
        pre2,pre1 = pre1,l
    else:print(l)

Solution (Python):
n = int(input())
L = [0 for i in range(n+2)]
L[0] = 2
L[1] = 1
for i in range(2, n+1):
    L[i] = L[i-1] + L[i-2]

print(L[n])

Solution (Python):
n = int(input())
l = [2, 1]
c = 2
while c < n+1:
    l.append(l[c-1]+l[c-2])
    c = c + 1
print(l[n])

Solution (Python):
n = int(input())
L0, L1 = 2, 1
while True:
    if n == 1:
        print(L1)
        exit()
    L0 += L1
    n -= 1
    if n == 1:
        print(L0)
        exit()
    L1 += L0
    n -= 1

Solution (Python):
l=[]
l.append(2)
l.append(1)

for i in range(85):
  l.append(l[i]+l[i+1])


N=int(input())


print(l[N])

Solution (Python):


def main():
    N = int(input())
    print(ryuka(N))

memo = {}

def ryuka(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    if n in memo:
        return memo[n]
    res = ryuka(n-1) + ryuka(n-2)
    memo[n] = res
    return res

main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    return


def B():
    return


def C():
    n = I()
    d = [None for i in range(n+1)]
    d[0] = 2
    d[1] = 1
    for i in range(2,n+1):
        d[i] = d[i-1]+d[i-2]
    print(d[n])
    return


def D():
    x,y,z = LI()
    for i in range(1000000)[::-1]:
        if i*y+(i+1)*z <= x:
            print(i)
            quit()
    return


def E():
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    h,w = LI()
    s = SR(h)
    for i in range(h):
        for j in range(w):
            if s[i][j] == "
                su = 0
                for dy,dx in d:
                    y = i+dy
                    x = j+dx
                    if 0 <= y < h and 0 <= x < w:
                        if s[y][x] == "
                            su += 1
                if su == 0:
                    print("No")
                    quit()
    print("Yes")
    return


def F():
    a,b,c,X,Y = LI()
    ans = float("inf")
    for z in range(300001):
        if z%2 == 0:
            m = c*z
            x = z//2
            y = z//2
            m += a*max(0,X-x)
            m += b*max(0,Y-y)
            if m < ans:
                ans = m
    print(ans)
    return


def G():
    n = I()
    x = LI()
    f = [(i,x[i]) for i in range(n)]
    f.sort(key = lambda x:x[1])
    g = [(f[i][0],i) for i in range(n)]
    g.sort(key = lambda x:x[0])
    for i in range(n):
        if g[i][1] < n//2:
            print(f[n//2][1])
        else:
            print(f[n//2-1][1])
    return


def H():
    return


def I_():
    return


def J():
    return


if __name__ == "__main__":
    C()

Solution (Python):
N = int(input())
lucas = [0]*(N+1)
lucas[0] = 2
lucas[1] = 1
for i in range(N-1):
    lucas[i+2] = lucas[i+1] + lucas[i]

print(lucas[N])

Solution (Python):
n = int(input())
l = [2,1]

if n == 1:
    print(1)

else:
    for i in range(2,n+1):
        l.append(int(l[i-1] +l[i-2]))
    print(l[n])

Solution (Python):


N = int(input())

r = [0 for i in range(87)]
r[0] = 2
r[1] = 1

def ryuka(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        if r[n] != 0:
            return r[n]
        r[n] = ryuka(n-1) + ryuka(n-2)
        return r[n]

print(ryuka(N))

Solution (Python):
l = [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324, 228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636, 4106118243, 6643838879, 10749957122, 17393796001, 28143753123, 45537549124, 73681302247, 119218851371, 192900153618, 312119004989, 505019158607, 817138163596, 1322157322203, 2139295485799, 3461452808002, 5600748293801, 9062201101803, 14662949395604, 23725150497407, 38388099893011, 62113250390418, 100501350283429, 162614600673847, 263115950957276, 425730551631123, 688846502588399, 1114577054219522, 1803423556807921, 2918000611027443, 4721424167835364, 7639424778862807, 12360848946698171, 20000273725560978, 32361122672259149, 52361396397820127, 84722519070079276, 137083915467899403, 221806434537978679, 358890350005878082, 580696784543856761, 939587134549734843, 1520283919093591604]
print(l[int(input())])

Solution (Python):
n=int(input())
L=[2,1]


for i in range(2,n+1):
    x=L[-1]+L[-2]
    L.append(x)

print(L[-1])

Solution (Python):
n = int(input())
l = [2,1]
if n == 1:
    print(1)
else:    
    for i in range(n-1):
        l.append(l[-1]+l[-2])
    print(l[-1])

Solution (Python):
n = int(input())
a = 2
b = 1
ans = 0
if n == 1:
    print(b)
else:
    for i in range(n-1):
        ans = a + b
        a = b
        b = ans
        
        
    print(ans)

Solution (Python):
N = int(input())
L = [2, 1]
for i in range(2, N + 1):
    L.append(L[-2] + L[-1])
print(L[-1])

Solution (Python):
n=int(input())
a=[]
a.append(2)
a.append(1)
for i in range(2,n+1):
 a.append(a[i-1]+a[i-2])
print(a[n])

Solution (Python):
N = int(input())

lucas = [2, 1]
for i in range(2, N+1):
    lucas.append(lucas[i-1] + lucas[i-2])

print(lucas[N])

Solution (Python):
N = int(input())

memo = [-1]*(N+1)


def ryuka(i):
    if i == 0:
        return 2
    elif i == 1:
        return 1
    else:
        if memo[i-1] != -1:
            ryuka1 = memo[i-1]
        else:
            ryuka1 = ryuka(i-1)
            memo[i-1] = ryuka1

        if memo[i-2] != -1:
            ryuka2 = memo[i-2]
        else:
            ryuka2 = ryuka(i-2)
            memo[i-2] = ryuka2

        return ryuka1 + ryuka2


print(ryuka(N))

Solution (Python):
A=[2,1]
for i in range(86):
    A.append(A[0+i]+A[1+i])
print(A[int(input())])

Solution (Python):
n=int(input())
l=[2,1]
for i in range(n-1):
    l.append(l[-1]+l[-2])
print(l[-1])

Solution (Python):
n=int(input())
l=[2,1]
for i in range(2,n+1):
    l.append(sum(l[-1:-3:-1]))
print(l[-1])

Solution (Python):
N = int(input())

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

print(L[N])

Solution (Python):
N=int(input())
L=[2,1]
for i in range(2,N+1):
    L.append(L[i-1]+L[i-2])
print(L[N])

Solution (Python):
import sys
n = int(input())
memo =[2,1]
for i in range(2,n+1):
    memo.append( memo[i-1]+memo[i-2] )
print(memo[n])

Solution (Python):
n = int(input())
a, b = 2, 1
for i in range(n):
  a, b = b, (a+b)
print(a)

Solution (Python):
from functools import reduce
import math

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input())
    L = [0]*(N+1)
    L[0] = 2
    L[1] = 1
    for i in range(2,N+1):
        L[i] = L[i-2]+L[i-1]
    print(L[N])
    
if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
l = [2,1]
for i in range(n-1):
  l.append(l[i] + l[i+1])
print(l[-1])

Solution (Python):
n=int(input())

count=1
sum=1
sum_old=2
sum_k=0

if n==0:
  print(2)
elif n==1:
  print(1)
else:
  while count<n:
    sum_k=sum
    sum+=sum_old
    sum_old=sum_k
    count+=1
  print(sum)

Solution (Python):
x = int(input())
l = [2,1]
for i in range(2,87):
  l.append(l[-1]+l[-2])
print(l[x])

Solution (Python):
n=int(input())
l=[2,1]

for i in range(2,n+1):
    l.append(l[i-2]+l[i-1])

print(l[-1])

Solution (Python):
a,b=2,1;exec'a,b=b,a+b;'*input();print a

Solution (Python):
n = int(input())
l = [2, 1]
for i in range(n-1):
  l.append(l[-1] + l[-2])
print(l[n])

Solution (Python):
n = int(input())
l = [2, 1]
if n == 1:
  print(1)
else:
  for i in range(2, n+1):
    l.append(l[i-1] + l[i-2])
  print(l[n])

Solution (Python):
N=int(input())
L=[]
L.append(2)
L.append(1)
for i in range(2,N+2):
	L.append(L[i-1]+L[i-2])
print(L[N])

Solution (Python):
n=int(input())
a,b=2,1
for i in range(n-1):
    a,b=b,a+b
print(b)

Solution (Python):
N = int(input())
L = [0] * 100

L[0] = 2
L[1] = 1

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

Solution (Python):
n = int(input())
a = [2,1]
for i in range(2,n+2):
    a.append(a[i-1]+a[i-2])
print(a[n])

Solution (Python):
N=int(input())

def memoize(f):
	memo = {}
	def func(n):
		if n not in memo:
			memo[n] = f(n)
		return memo[n]
	return func

@memoize
def lucas(n):
	if n < 2:
		return [2, 1][n]
	return lucas(n-1) + lucas(n-2)

print(lucas(N))

Solution (Python):
lukas=[2,1]
for i in range(2,90):
    lukas.append(lukas[i-2]+lukas[i-1])

print(lukas[int(input())])

Solution (Python):
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

a = {}
a[0] = 2
a[1] = 1
def lucas(n):
    if n in a:
        return a[n]
    
    a[n] = lucas(n-1) + lucas(n-2)
    return a[n]



def solve():
    n = f()[0]
    print(lucas(n))



solve()

Solution (Python):
N = int(input())
L = [2,1]
for i in range(2,N+1):
    L.append(L[i-1]+L[i-2])
print(L[N])

Solution (Python):
a,b = 2,1
for i in range(int(input())):
    a,b = b,(a+b)
print(a)

Solution (Python):
N = int(input())
L = [2,1]
for i in range(2,N+1):
    L.append(L[i-1]+L[i-2])
print(L[N])

Solution (Python):

def read_input():
    n = int(input())
    return n


def lucas(n, l1, l2):
    if n == 0:
        return l2
    return lucas(n - 1, l2 + l1, l1)

def submit():
    n = read_input()
    print(lucas(n, 1, 2))

if __name__ == '__main__':
    submit()

Solution (Python):
N = int(input())

def Luca(k,x,y):
    if k == N:
        return y
    else:
        return Luca(k+1,y,x+y)

print(Luca(1,2,1))

Solution (Python):
n = int(input())
arr = [2, 1]
index = 0
while len(arr) <= 86:
    arr.append(arr[index] + arr[index + 1])
    index += 1

print(arr[n])

Solution (Python):
L =[2,1]
n = int(input())
for i in range(2,n+1):
    L.append(L[i-1] + L[i-2])
print(L[-1])

Solution (Python):


import sys
import math


Ns = [2,1]
for i in range(86):
  Ns.append(Ns[-1]+Ns[-2])

n = int(input())
print(Ns[n])

Solution (Python):
N = int(input())
a, b = 2, 1
for _ in range(N):
    a, b = b, a + b
print(a)

Solution (Python):
N = int(input())
l = [2, 1]
for i in range(1, N):
    l.append(l[i-1] + l[i])
print(l.pop())

Solution (Python):
n = int(input())
l = [2, 1,]

if n <= 1:
    print(l[n])
else:
    for i in range(2, n+1):
        calc = l[i-2] + l[i-1]
        l.append(calc)
    print(l[n])

Solution (Python):
L = [2,1]
while len(L) < 90:
    L.append(L[-2] + L[-1])
print(L[int(input())])

Solution (Python):

n = int(input())
def lucas(n, a=2, b=1):
    if n == 0:
        return a
    elif n == 1:
        return b
    else:
        return lucas(n - 1, b, a + b)

print(lucas(n))

Solution (Python):
N = int(input())
L = [2,1]
for i in range(N-1):
    L.append(L[-1]+L[-2])
print(L[N])

Solution (Python):

n=int(input())
l=[2,1]

for i in range(2,n+1):
    l.append(l[i-2]+l[i-1])

print(l[-1])

Solution (Python):
import sys
from collections import Counter

n = int(input())
if n == 0:
    print(2)
    sys.exit()
elif n == 1:
    print(1)
    sys.exit()
l_list = [2, 1]
i = 2

while True:
    l_list.append(l_list[i-1] + l_list[i-2])
    if len(l_list) - 1 == n:
        print(l_list[-1])
        sys.exit()
    i += 1

Solution (Python):
N = int(input())
L = [2,1]
for i in range(2,N+1):
    L.append(L[i-2]+L[i-1])
print(L[-1])

Solution (Python):
L = [0] * 87
L[0] = 2
L[1] = 1

for i in range(2, 87):
    L[i] = L[i-1] + L[i-2]

print(L[int(input())])

Solution (Python):
N = int(input())

Luca = [2, 1]
for i in range(N-1):
  Luca[1], Luca[0] = Luca[0]+Luca[1], Luca[1]

print(Luca[1])

Solution (Python):
N = int(input())

l = [2, 1]
ans = 1
for i in range(1, N):
    ans = l[0] + l[1]
    l[0], l[1] = l[1], ans

print(ans)

Solution (Python):
N = int(input())
L = [0] * 87  
L[0] = 2
L[1] = 1
if N >= 2:
	for i in range(2, N + 1):
		L[i] = L[i - 1] + L[i - 2]
print(L[N])

Solution (Python):
n = int(input())
def lucas(x):
    a = 2
    b = 1
    for i in range(x):
        a,b = b,a+b
    return a
print(lucas(n))

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

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())

pre = 2
ans = 1
for i in range(n-1):
    temp = ans
    ans = pre + ans
    pre = temp
    
print(ans)

Solution (Python):
N = int(input())
L = [2,1]
for i in range(2,N+1):
    L.append(L[i - 2] + L[i - 1])

print(L[N])

Solution (Python):
n=int(input())
def func(n):
    a=2
    b=1
    for i in range(n):
        a,b=b,a+b
    return a
print(func(n))

Solution (Python):
def Lucas(n):
    if len(l)>n:return l[n]
    l.append(Lucas(n-1)+Lucas(n-2))
    return l[-1]

l=[2,1]
print(Lucas(int(input())))

Solution (Python):
n = int(input())

a = 2
b = 1
l = 1
for i in range(n+1):
    if i == 0 or i == 1:
        a = 2
        b = 1
    else:
        l = a + b
        a = b
        b = l

print(l)

Solution (Python):
n=int(input())
l=[2,1]
for i in range(n-1):
    l[i%2]=l[0]+l[1]
print(l[n%2])

Solution (Python):
M=[0]*100
M[0]=2
M[1]=1

def Lucas(i):
  if M[i]!=0:
    return M[i]
  else:
    M[i]=Lucas(i-1)+Lucas(i-2)
    return M[i]
  
print(Lucas(int(input())))

Solution (Python):
N = int(input())

L = [2, 1]

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

Solution (Python):
N = int(input())
a = 2
b = 1
for i in range(N) :
    a,b = b,a+b
print(a)

Solution (Python):
RN = [2, 1]
for i in range(2, 86 + 1):
	RN += [RN[i-1] + RN[i-2]]
print(RN[int(input())])

Solution (Python):
N = int(input())
lucas = [2, 1]
for i in range(2, N + 1):
    lucas.append(lucas[i - 1] + lucas[i - 2])

print(lucas[N])

Solution (Python):
n=int(input())
l=[2,1]
for i in range(2,90):
    l.append(l[i-1]+l[i-2])

print(l[n])

Solution (Python):
N = int(input())
ryukasu = [2, 1]
for i in range(2, N+1):
    ryukasu.append(ryukasu[i - 1] + ryukasu[i - 2])
print(ryukasu[-1])

Solution (Python):
N = int(input())
L = [2, 1]
for i in range(2, 87):
    L.append(L[i-2] + L[i-1])
print(L[N])

Solution (Python):
n=int(input())
list=[0]*(n+1)
list[0]=2
list[1]=1
for i in range(2,n+1):
  list[i]=list[i-1]+list[i-2]
print(list[n])

Solution (Python):
n=int(input())
L=[2,1]
if n<2:
  print(L[-1])
else:
  for i in range(n-1):
    L.append(L[i]+L[i+1])
  print(L[-1])

Solution (Python):
n=int(raw_input())

if n==0:
	print(2)
elif n==1:
	print(1)
ln=[2,1]
if n >=2:
	for i in range(2,n+1):
		ln.append(ln[i-1]+ln[i-2])	
	print(ln[-1])

Solution (Python):
N = int(input())
l = [2, 1]
for i in range(85):
    l.append(l[i] + l[i + 1])
print(l[N])

Solution (Python):
n = int(input())

if n == 1:
  print(1)
else:
  a, b = 2, 1
  for i in range(n - 1):
    a, b = b, a + b
  print(b)

Solution (Python):
l = [2,1]
n = int(input())
for i in range(2,n+1):
    l.append( l[-1] + l[-2] )
print(l[n])

Solution (Python):
a, b = 2, 1
N = int(input())
for _ in range(N):
    a, b = b, a+b
print(a)

Solution (Python):
n = int(raw_input())
L0 = 2; L1 = 1
if n == 1:
	print L1
else:
	for i in range(n - 1):
		L2 = L1 + L0
		L0 = L1
		L1 = L2
	print L2

Solution (Python):
N = int(input())

luca = [2,1]

while len(luca) <= N:
    luca.append(luca[-2] + luca[-1])

print(luca[N])

Solution (Python):
def solve():
    L=[0]*90
    L[0]=2
    L[1]=1
    for i in range(2,87):
        L[i]=L[i-1]+L[i-2]
    N=int(input())
    return L[N]

print(solve())

Solution (Python):
N = int(input())

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

Solution (Python):
n = int(input())
l = [0] * 87

l[0] = 2
l[1] = 1
for i in range(2, 87):
    l[i] = l[i-1] + l[i-2]
print(l[n])

Solution (Python):
N = int(input())

if N==0:
    print(2)
elif N == 1:
    print(1)
else:
    a = 2
    b = 1
    for i in range(2, N+1):
        c = b + a
        b, a = c, b
    print(c)

Solution (Python):
n = int(input())
lucas = [2,1]
for i in range(2,100):
	lucas.append(lucas[i-1]+lucas[i-2])
print(lucas[n])

Solution (Python):
N=int(input())
L=[2,1] 
for i in range(N-1) :
  A=L[i]+L[i+1]
  L.append(A)
print(L[-1])

Solution (Python):
n=int(input())
l=[0]*(n+1)
l[0]=2;l[1]=1
for i in range(2,n+1):
  l[i]=l[i-1]+l[i-2]
print(l[-1])

Solution (Python):
n = int(input())

l_i = 0
l_i_1 = 1
l_i_2 = 2

if n == 1:
  print("1")
else:
  for i in range(n-1):
    l_i = 0
    l_i = l_i_1 + l_i_2
    l_i_2 = l_i_1
    l_i_1 = l_i
  print(l_i)

Solution (Python):
n = int(input())

l1 = 2
l2 = 1
l3 = 3

if n >= 2:
    for i in range(n - 1):
        t = l1 + l2
        l1 = l2
        l3 = t
        l2 = l3
    print(l3)
else:
    if n == 1:
        print(l2)
    else:
        print(l1)

Solution (Python):
N = int(input())

L0 = 2
L1 = 1

i = N
while i-1 > 0:
    Ln = L0 + L1
    i -= 1
    L0 = L1
    L1 = Ln

if N == 0:
    print(2)
elif N == 1:
    print(1)
else:
    print(Ln)

Solution (Python):
n = int(input())
l = [0] * 100
l[0] = 2
l[1] = 1
for i in range(2, n+1):
    l[i] = l[i-1] + l[i-2]
print(l[n])

Solution (Python):
n = int(input())
L = [2,1]
for i in range(100):
    L.append(L[-1]+L[-2])
print(L[n])

Solution (Python):
from functools import lru_cache

@lru_cache(maxsize=1000)
def lucas(i):
    if i == 0:
        return 2
    if i == 1:
        return 1
    return lucas(i - 1) + lucas(i - 2)

print(lucas(int(input())))

Solution (Python):
N = int(input())

l = [2] + [0] * N
l[1] = 1
for i in range (2, N+1):
    l[i] = l[i-1] + l[i-2]
print(l[-1])

Solution (Python):
N = int(input())
L = [2, 1]
for i in range(2, N+2):
    Li = L[i-1] + L[i-2]
    L.append(Li)
print(L[N])

Solution (Python):
N = int(input())
L = [2, 1]
for i in range(2, N+1):
    L.append(L[i-1] + L[i-2])
print(L[N])

Solution (Python):
N = int(input())
l = [2,1]
for i in range(2,N+1):
    l.append(l[i-2]+l[i-1])
print(l[N])

Solution (Python):
n = int(input())
memo = [0] * 87
memo[0] = 2
memo[1] = 1
for i in range(2, n+1):
    memo[i] = memo[i-1] + memo[i-2]
print(memo[n])

Solution (Python):
n = int(input())
a = 2
b = 1
for i in range(1,n):
  b, a = a+b, b
print(b)

Solution (Python):
N = int(input())

d_l = {0: 2, 1: 1}
def l(n):
    if n in d_l:
        return d_l[n]
    d_l[n] = l(n - 2) + l(n - 1)
    return d_l[n]

print(l(N))

Solution (Python):
a0=2
a=1
for _ in range(1,int(input())):
  a+=a0
  a0=a-a0
print(a)

Solution (Python):
N = int(input())
L = [2, 1]
for i in range(2, N+1):
    l = L[i-1] + L[i - 2]
    L.append(l)
print(L[N])

Solution (Python):
def solve(string):
    lucas = [2, 1]
    for i in range(2, 87):
        lucas.append(sum(lucas[-2:]))
    return str(lucas[int(string)])


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
L={0:2,1:1}
N=int(input())
for i in range(2,N+1):
    L[i]=L[i-1]+L[i-2]
print(L[N])

Solution (Python):
n = int(input())

l0 = 2
l1 = 1

for i in range(n):
    tmp = l1
    l1 = l1 + l0
    l0 = tmp

print(l0)

Solution (Python):
from sys import stdin
from functools import lru_cache
n = int(stdin.readline().rstrip())
@lru_cache(maxsize=86)
def lucas(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        return lucas(n-1)+lucas(n-2)

print(lucas(n))

Solution (Python):
def solve(n):
    L=[2,1]
    for i in range(2,n+1):
        tmp=L[i-2]+L[i-1]
        L=L+[tmp]
    return L[n]

N=int(input())
print(solve(N))

Solution (Python):
n=int(input())
L=[2,1]
for i in range(n):
    L.append(L[i]+L[i+1])
print(L[n])

Solution (Python):
N = int(input())

dp = [0] * (N+10)
dp[0] = 2
dp[1] = 1

for i in range(2,N+1):
  dp[i] = dp[i-1] + dp[i-2]

print(dp[N])

Solution (Python):
n = int(input())
dp = [2,1]

for i in range(2,n+1):
    d = dp[i-1]+dp[i-2]
    dp.append(d)
print(dp[n])

Solution (Python):


n = int(input())

lucas = [0] * 100
lucas[0] = 2
lucas[1] = 1

for i in range(2,n+1):
    lucas[i] = lucas[i-1] + lucas[i-2]
    if n == i:
        print(lucas[i])
        break

if n == 1:
    print(1)

Solution (Python):
N = int(input())

L = [2, 1]

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

Solution (Python):
n=int(input())
hoge=[2,1]

for i in range(n):
  hoge.append(hoge[-1]+hoge[-2])

print(hoge[n])

Solution (Python):
N = int(input())
c = [2] + [1] + [0] * (N - 1)
if N <= 1:
    print(c[N])
else:
    for i in range(2, N + 1):
        
        c[i] = c[i - 1] + c[i - 2]
    print(c[N])

Solution (Python):
N = int(input())
lucas = [2, 1]
for n in range(2, 87):
    lucas.append(lucas[n-1]+lucas[n-2])
print(lucas[N])

Solution (Python):
N = int(input())

lucas_memo = {}
def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        if n-1 in lucas_memo:
            ln1 = lucas_memo[n-1]
        else:
            ln1 = lucas(n-1)
            lucas_memo[n-1] = ln1
        if n-2 in lucas_memo:
            ln2 = lucas_memo[n-2]
        else:
            ln2 = lucas(n-2)
            lucas_memo[n-2] = ln2
        return ln1 + ln2

print(lucas(N))

Solution (Python):
n = int(input())
memo = [0] * (n+1)
def luca(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    if memo[n] != 0:
        return memo[n]
    memo[n] = luca(n-1) + luca(n-2)
    return memo[n]


print(luca(n))

Solution (Python):
N = int(input())
L = [2,1]
for i in range(2,N+1):
    L.append(L[i-1]+L[i-2])
print(L[-1])

Solution (Python):
ruca = [0] * 87
ruca[0] = 2
ruca[1] = 1
for i in range(2, 87):
    ruca[i] = ruca[i - 1] + ruca[i - 2]
print(ruca[int(input())])

Solution (Python):
N = int(input())
L = []
L.append(2)
L.append(1)
for i in range(2, N+1):
    a = L[i-1]
    b = L[i-2]
    L.append(a+b)
print(L[N])

Solution (Python):


N = int(input())
ans=[]
for i in range(N+1):
    if i==0:
        ans.append(2)
    elif i==1:
        ans.append(1)
    else:
        ans.append(ans[i-2]+ans[i-1])
print(ans[-1])

Solution (Python):
N = int(input())
L = [0] * (N + 1)
L[0] = 2
L[1] = 1
for i in range(2,N+1):
  L[i] = L[i-1]+L[i-2]
print(L[N])

Solution (Python):
n,a=int(input()),[2,1]
def lucas(i):
  global a
  return a[i-2]+a[i-1]
for i in range(n-1):a.append(lucas(i+2))
print(a[-1])

Solution (Python):
n=int(input())
l=[2,1]
for i in range(2,n+1):
    x=l[i-2]+l[i-1]
    l.append(x)
print(l[n])

Solution (Python):
N = int(input())
if N==1:
    print(1)
else:
    L1 = 2
    L2 = 1
    L3 = L1+L2
    while N!=2:
        L1 = L2
        L2 = L3
        L3 = L1+L2
        N-=1
    print(L3)

Solution (Python):
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

@functools.lru_cache(maxsize=None)
def Luca(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return Luca(n-1)+Luca(n-2)

N = I()
print(Luca(N))

Solution (Python):
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

@functools.lru_cache(maxsize=None)
def Luca(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return Luca(n-1)+Luca(n-2)

N = I()
print(Luca(N))

Solution (Python):
luca=[0]*87
luca[0]=2
luca[1]=1
for i in range(2,87):
  luca[i]=luca[i-1]+luca[i-2]
n=int(input())
print(luca[n])

Solution (Python):
N = int(input())

d2 = 2
d1 = 1
if N == 1:
    print(1)
else:
    for i in range(N):
        x = d1
        d1 += d2
        d2 = x
    print(d2)

Solution (Python):
n = int(input())
l = [0]*(n+1)
l[0] = 2
l[1] = 1
for i in range(2,n+1):
    l[i] = l[i-1]+l[i-2]
print(l[n])

Solution (Python):
lst = [2, 1]
N = int(input())
for n in range(2, N + 1):
    lst.append(lst[n - 1] + lst[n - 2])
print(lst[N])

Solution (Python):
N = int(input())

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

ans = Ls[-1]

print(ans)

Solution (Python):


import itertools
import collections
import bisect

def main():
    N = int(input())

    L = [0] * 90
    L[0] = 2
    L[1] = 1
    for i in range(2, 87):
        L[i] = L[i-1] + L[i-2]
    print(L[N])


if __name__ == '__main__':
    main()

Solution (Python):
L=[2,1]
for i in range(86):
  L.append(L[-1]+L[-2])
print(L[int(input())])

Solution (Python):
N = int(input())
luka = [2, 1]
if N==1: 
    print(1)
    exit()
for i in range(N-1):
    luka.append(luka[-1]+luka[-2])
print(luka[N])

Solution (Python):
def lucas_number(N: int) -> int:
    l0, l1 = 2, 1
    if N == 0:
        return l0
    if N == 1:
        return l1

    l = 0
    for _ in range(1, N):
        l = l1 + l0
        l1, l0 = l, l1
    return l


if __name__ == "__main__":
    N = int(input())
    ans = lucas_number(N)
    print(ans)

Solution (Python):
a,b=2,1;exec('a,b=b,a+b;'*int(input()));print(a)

Solution (Python):
N = int(input())

L = [0] * (N+1)
L[0] = 2
L[1] = 1

for i in range(2, N+1):
    L[i] = L[i-1] + L[i-2]

print(L[N])

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    if N == 0:
        print(2)
        return 0
    if N == 1:
        print(1)
        return 0

    lucas = [0] * (N+1)
    lucas[0] = 2
    lucas[1] = 1
    for i in range(2, N+1):
        lucas[i] = lucas[i-2] + lucas[i-1]

    print(lucas[N])


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
L = [2,1]
for i in range(N - 1) :
    A = int(L[-1]) + int(L[-2])
    L.append(A)
print(L[-1])

Solution (Python):
N = int(input())

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

Solution (Python):
n=int(input())
a=[2,1]
for i in range(87):
    a.append(a[i]+a[i+1])  
print(a[n])

Solution (Python):
n = int(input())

l = [0] * 87
l[0] = 2
l[1] = 1
for i in range(2, n + 1):
    l[i] = l[i-1] + l[i-2]
print(l[n])

Solution (Python):
N = int(input())
L = {-1: -1, 0: 2}
for i in range(1, N + 1):
    L[i] = L[i - 1] + L[i - 2]
print(L[N])

Solution (Python):
n = int(input())
if n == 1:
    print(1)
else:
    l0, l1 = 2, 1
    for i in range(n-1):
        l2 = l1 + l0
        l0, l1 = l1, l2
    print(l2)

Solution (Python):
n = int(input())

a = [2,1]
for i in range(2,n+1):
    a.append(a[-1]+a[-2])

print(a[-1])

Solution (Python):
N = int(input())
Ns = [2,1]
for i in range(2,N+1):
    Ns.append(Ns[i-1]+Ns[i-2])
print(Ns[-1])

Solution (Python):
a,b=2,1
n=int(input())
for _ in range(n-1):
  t=b
  b=a+b
  a=t
print(b)

Solution (Python):
N=int(input())
A=2
B=1
i=1
for i in range(N):
    C=A+B
    A=B
    B=C
    i+=1
print(A)

Solution (Python):
N = int(input())
dp = [0]*(N+1)
dp[0] = 2
dp[1] = 1
for i in range(2,N+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N])

Solution (Python):

import sys

def main():
	N = int(input())
	nums = [0 for _ in range(N)]
	
	if N == 0:
		print(2)
		sys.exit()
	if N == 1:
		print(1)
		sys.exit()
		
	nums[0] = 2
	nums[1] = 1
	for i in range(N):
		if i < 2:
			continue
		nums[i] = nums[i-1] + nums[i-2]
	
	print(nums[N-1] + nums[N-2])
	
if __name__ == "__main__":
	main()

Solution (Python):
def main():
    N = int(input())
    L = [0] * (N+1)
    L[0] = 2
    L[1] = 1
    for i in range(2, N+1):
        L[i] = L[i-1] + L[i-2]
    print(L[N])


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
L = [2, 1]
for i in range(2, N+1):
  L.append(L[i-1]+L[i-2])
print(L[N])

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
lucas = [0]*(N+1)
lucas[0] = 2
lucas[1] = 1

for i in range(2, N+1):
    lucas[i] = lucas[i-1]+lucas[i-2]
print(lucas[-1])

Solution (Python):
n = int(input())
lucas = [0] * (n+1)
lucas[0] = 2
lucas[1] = 1
for i in range(2, n+1):
    lucas[i] = lucas[i-1] + lucas[i-2]
print(lucas[n])

Solution (Python):
a = [2,1]
for i in range(int(input())-1):
    a.append(a[-1]+a[-2])
print(a[-1])

Solution (Python):
n = int(input())
a = [2,1]
for i in range(2,n+1):
    a.append(a[i-1]+a[i-2])
print(a[-1])

Solution (Python):
N = int(input())
Lucas = [2,1]

if(N >= 2):
  for i in range(N-1):
    Lucas.append(Lucas[i] + Lucas[i+1])

print(Lucas[N])

Solution (Python):
n=int(input())
Lucas=[2,1]
if n>=2:
    for i in range(n-1):
        Lucas.append(Lucas[i]+Lucas[i+1])
print(Lucas[n])

Solution (Python):
n=int(input())
if n==1:print(1)
elif n==2:print(3)
else:
    ans=3
    befor=1
    for i in range(n-2):
        a=befor
        befor=ans
        ans+=a
    print(ans)

Solution (Python):

INF=1e18
MOD=1e9+7

N=int(input())

l=[0]*100
l[0]=2
l[1]=1

for i in range(2, N+1):
    l[i]=l[i-1]+l[i-2]

print(l[N])

Solution (Python):

N = int(input())
L = [0] * 87
L[0] = 2
L[1] = 1
for i in range(2, N + 1):
  L[i] = L[i - 1] + L[i - 2]
print(L[N])

Solution (Python):
N = int(input())


def lc():
    l0, l1 = 2, 1
    while 1:
        yield l0 + l1
        l0, l1 = l1, l0 + l1


if N > 1:
    for i, n in enumerate(lc()):
        if i == N - 2:
            print(n)
            break
else:
    print(1)

Solution (Python):
first=2
second=1
cnt=1
n=int(input())
while cnt<n:
    first,second=second,first+second
    cnt+=1
print(second)

Solution (Python):
n=int(input())

X=[0]*(n+1)
X[0]=2
X[1]=1
for i in range(2,n+1):
    X[i]=X[i-1]+X[i-2]

print(X[n])

Solution (Python):
n = int(input())
l = [2,1]

for i in range(2,87):
    x = l[i-2] + l[i-1]
    l.append(x)

print(l[n])

Solution (Python):
n=int(input())
l=[2,1]
for i in range(2,87):
  x=l[i-2]+l[i-1]
  l.append(x)
print(l[n])

Solution (Python):
n = int(input())
if n == 0:
    print(2)
    exit()
if n == 1:
    print(1)
    exit()
l = [2, 1] + [0]*(n-1)
for i in range(2, n+1):
    l[i] = l[i-2] + l[i-1]
print(l[-1])