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):
def LucasNumber(N):
    if N==0:
        return 2
    elif N==1:
        return 1
    else:
        Li2 = 2
        Li1 = 1
        for T in range(2,N+1):
            Li0 = Li1+Li2
            Li2 = Li1
            Li1 = Li0
        return Li0
      
print(LucasNumber(int(input())))

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

Solution (Python):


n = int(input())
a=[2,1]
a_tes = 0

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

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

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

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

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

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

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

Solution (Python):
s= int(input())
L0 = 2
L1 = 1
L = 0
if s ==1:
  print(L1)
else:
  for i in range(2,s+1):
    L = L0 + L1
    L0 = L1
    L1 = L
  print(L)

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

lucas_list = [2, 1]
for i in range(2, 86+1):
    lucas_list.append(lucas_list[i-1] + lucas_list[i-2])
    
print(lucas_list[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):
def resolve():
    N = int(input())
    lic = [2, 1]
    for i in range(85):
        lic.append(lic[-1]+lic[-2])
    print(lic[N])
resolve()

Solution (Python):
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def main():
    n = int(input())
    pre = 2
    now = 1
    for _ in range(n):
        pre, now = now, now + pre
    print(pre)


if __name__ == "__main__":
    main()

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=[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())
a=2
b=1
for _ in range(n-1):
    a,b=b,a+b
print(b)

Solution (Python):
memo = {0:2, 1:1}

n = int(input())

for number in range(2,n+1):
  memo[number] = memo[number-1] +  memo[number-2]
  
print(memo[n])

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

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

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

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

from collections import defaultdict
d = defaultdict(lambda: -1)		

d[0] = 2
d[1] = 1
def f(n):
  if d[n] == -1:
    a = f(n-1) + f(n-2)
    d[n] = a
  return d[n]

print(f(N))

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

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

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

Solution (Python):
li = [2,1]
for i in range(86):
    li.append(li[i]+li[i+1])
n = int(input())
print(li[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):
s = input()
n = int(s)

lucas = [2, 1]

x = 0

index = 0

while (index < n):
    x = lucas[index] + lucas[index + 1]
    lucas.append(x)
    index += 1

print(lucas[index])

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

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

A = [2,1]

for i in range(2,90):
  temp = A[i-1]+A[i-2]
  A.append(temp)
ans = A[N]
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

print(dp[N])

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

Solution (Python):
memo = {}
def f(x):
    if x==0:
        return 2
    if x==1:
        return 1
    if x in memo:
        return memo[x]
    memo[x] = f(x-1)+f(x-2)
    return memo[x]
print(f(int(input())))

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[N])

Solution (Python):
n = int(input())
l = [0]*(n+1)
l[0]=2
l[1]=1
def lucas_number(n):
    global l
    if l[n]!=0:
        return l[n]
    l[n] = lucas_number(n-1)+lucas_number(n-2)
    return l[n]
print(lucas_number(n))

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())

L = [2, 1]

if N == 1:
  print(L[1])
  exit()
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 = [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())
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())
l0,l1 = 2,1
l2 = l1
for i in range(N-1):
    l2 = l0 + l1
    l0 = l1
    l1 = l2
    
print(l1)

Solution (Python):
N = int(input())
a, b = 2, 1

for i in range(N - 1):
    a, b = b, (a + b)
print(b)

Solution (Python):
import sys
def I():
    return int(sys.stdin.readline().rstrip())

N = I()

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

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

Solution (Python):
n = int(input())
l_list = [2, 1]
if n < 2 :
    print(l_list[n])
else :
    for i in range(2,n+1) :
        new = l_list[i-1] + l_list[i-2]
        l_list.append(new)
    print(l_list[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):
def solve():
    N = int(input())
    L = [0 for _ in range(N+1)]
    L[0] = 2
    L[1] = 1
    for i in range(N-1):
         L[i+2] = L[i+1] + L[i]
    print(L[N])







if __name__ == "__main__":
    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):
N = int(input())
R = [2, 1]
if N < 2:
    print(R[N])
    exit()
for i in range(2, N+1):
    R.append(R[i-1] + R[i-2])
print(R[N])

Solution (Python):
N = int(input())
R = [None] * (N+1)

R[0] = 2
if N == 0:
    print(R[0])
    exit()
R[1] =1
if N == 1:
    print(R[1])
    exit()
if N >= 2:
    for i in range(2, N+1):
        R[i] = R[i-1] + R[i-2]
    print(R[N])

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

Solution (Python):
cache = {}

def main():
    def lucas(x):
        if x == 0:
            return 2
        elif x == 1:
            return 1
        elif x in cache:
            return cache[x]
        else:
            cache[x] = lucas(x-1) + lucas(x-2)
            return cache[x]

    N = int(input())
    print(lucas(N))


if __name__ == '__main__':
    main()

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

ans = L[N]
print(ans)

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

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())
L = [2,1,3]
if N >= 3:
  for i in range(N-2):
    L[0] = L[1]
    L[1] = L[2]
    L[2] = L[0] + L[1]
  print(L[2])
else:
  print(L[N])

Solution (Python):
l,m=2,1
for _ in range(int(input())): l,m=m,l+m
print(l)

Solution (Python):
a=[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(a[int(input())])

Solution (Python):
l=[2,1]
for _ in range(85): l+=[l[-2]+l[-1]]
print(l[int(input())])

Solution (Python):
N = int(input())
L = [2, 1]
i = 1
while i < N:
    i += 1
    L[0], L[1] = L[1], L[0]+L[1]
print(L[1])

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

a = 2
b = 1
ans = 0

if N == 1:
  ans = 1
else:
  for i in range(N-1):
    b, a = a + b, b
    ans = b

print(ans)

Solution (Python):
n = int(input())
i, a, b = 2, 2, 1
ans = 0
if n==1:
  print(1)
  quit()
while i <= n:
  ans = a + b
  a,b = b, ans
  i += 1
print(ans)

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

from collections import defaultdict
d = {0:2,1:1}

def calc(n):
    if n not in d:
        d[n] = calc(n-1) + calc(n-2)
    return d[n]

for i in range(n):
    calc(i)

print(calc(n))

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

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue

from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    L0, L1 = 2, 1

    for n in range(N):
        L0, L1 = L1, L1 + L0
    print(L0)


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
nums=[2, 1]
for _ in range(N-1):
  nums=[nums[1], nums[0]+nums[1]]
print(nums[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[N])

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

def ryuca_memo(n):
    memo = [0]*(n+1)
    def _ryuca(n):
        if n == 1:
            return 1
        elif n == 0:
            return 2
        if memo[n] != 0:
            return memo[n]
        memo[n] = _ryuca(n-1) + _ryuca(n-2)
        return memo[n]
    return _ryuca(n)

print(ryuca_memo(N))

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

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

print(res[-1])

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

Solution (Python):

import sys
sys.setrecursionlimit(50000)
def ryuka(n):
    dp = [0]*(n+1)
    
    def ryu(n):
        if n < 2:
            return 2 - n
        if dp[n] != 0:
            return dp[n]
        dp[n] = ryu(n-1)+ryu(n-2)
        return dp[n]

    return ryu(n)
print(ryuka(int(input())))

Solution (Python):
N = int(input())
L0 = 2
L1 = 1

if N==1:
  print(1)

else:
  for n in range(N-1):
    L = L0+L1
    L0 = L1
    L1 = L
  print(L)

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

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

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

print(a)

Solution (Python):












N = int(input())

Li_2 = 2
Li_1 = 1
Li = 1

for i in range(2, N + 1):
    Li = Li_1 + Li_2
    Li_2, Li_1 = Li_1, Li

print(Li)

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

for i in range(n+1):
    if i == 0:
        l.append(2)
    elif i == 1:
        l.append(1)
    else:
        l.append(l[-1]+l[-2])

print(l[n])

Solution (Python):
def calc(n):
    if res[n] != 0:
        return res[n]
    tmp = calc(n-1) + calc(n-2)
    res[n] = tmp
    return tmp

N = int(input())
res = [0] * 100
res[0] = 2
res[1] = 1
calc(N)
print(res[N])

Solution (Python):
N = int(input())
l0 = 2
l1 = 1
for _ in range(2, N+1):
    l0, l1 = l1, l0+l1

print(l1)

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

print(lst[-1])

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

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations,accumulate 

from collections import deque,defaultdict,Counter
import decimal
import re











import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return 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[I()])

Solution (Python):
def solve():
    ans = 0
    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]
    return dp[-1]
print(solve())

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

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

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

Solution (Python):
memo = {}
def f(i):
    if i==0:
        return 2
    if i==1:
        return 1
    if i in memo:
        return memo[i]
    memo[i] = f(i-1)+f(i-2)
    return memo[i]
print(f(int(input())))

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

dp = [2, 1]

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

print(dp[-1])

Solution (Python):
N= int(input())
L0=2
L1=1
if N == 0:
  print(2)
elif N == 1:
  print(1)
else:
  for i in range(2,N+1):
    L=L0+L1
    L0 = L1
    L1 = L
  print(L)

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):
n = int(input())

l2 = 1
l1 = 2

if n == 0:
    l2 = l1
elif n == 1:
    pass
else:
    for i in range(n-1):
        l0 = l1
        l1 = l2
        l2 = l1 + l0

print(l2)

Solution (Python):










import sys

def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]

def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)


N = iIn()

A = [2, 1]

for i in range(N):
  var = A[-2] + A[-1]
  A.append(var)
  
print(A[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())
lucas_number = [0] * (n + 1)
lucas_number[0] = 2
lucas_number[1] = 1
for i in range(2, n + 1):
    lucas_number[i] = lucas_number[i - 1] + lucas_number[i - 2]
print(lucas_number[n])

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

l = [0] * (n+1)

for i in range(n+1):
  if i == 0:
    l[0] = 2
  elif i == 1:
    l[1] = 1
  else:
    l[i] = l[i-2] + l[i-1]
    
print(l[n])

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

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

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

if n == 1:
  print(1)
  exit()
  
nums = [0]*(n+1)
nums[0] = 2
nums[1] = 1

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

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 - 2] + lucas[i - 1]

print(lucas[n])

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


def read():
    N = int(input().strip())
    return N,


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


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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

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

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


def f(i):
    if i == 0:
        return 2
    if i == 1:
        return 1
    if L[i] == 0:
        L[i] = f(i - 1) + f(i - 2)
    return L[i]


print(f(N))

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue

from decimal import Decimal
from collections import defaultdict, deque



sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    L = [0] * (N + 3)
    if N == 0:
        print(2)
        exit()
    L[0] = 2
    if N == 1:
        print(1)
        exit()
    L[1] = 1
    for n in range(2, N+1):
        L[n] = L[n - 1] + L[n - 2]
    print(L[n])


if __name__ == '__main__':
    main()

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

Solution (Python):
n=int(input())
l_b=2
l=1
if n==0:
  print("2")
elif n==1:
  print("1")
else:
  for i in range(2,n+1):
    l_bb=l_b
    l_b=l
    l=l_b+l_bb
  print(l)

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

Solution (Python):
import numpy
a=numpy.matrix
print(int((a([[1,1],[1,0]])**int(input())@a([[1],[2]]))[1]))

Solution (Python):
import sys
N = int(input())
if not (1 <= N <= 86):
    sys.exit()

L = [2,1]
if N == 1:
    print(1)
    sys.exit()

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

Solution (Python):









import sys
input = sys.stdin.readline

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

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

Solution (Python):

from functools import lru_cache

n = int(input())

@lru_cache(maxsize=None)
def lucas(n):
    if n == 1:
        return 2
    elif n == 2:
        return 1
    else:
        return lucas(n-2)+lucas(n-1)
    

print(lucas(n+1))

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

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

Solution (Python):
a = [2, 1]
n = int(input())
while(len(a) != n+1):
  a.append(a[-1] + a[-2])
print(a[-1])

Solution (Python):
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())

n = i()
ls = [2,1]
i = 2
def lucas(n):
	global i
	if n == 0:
		return 
	else:
		n -= 1
		memo = ls[i-2] + ls[i-1]
		ls.append(memo)
		i += 1
		lucas(n)			

lucas(86)
print(ls[n])

Solution (Python):
def Lucas_Update(L0,L1):
    L2=L0+L1
    return L2
N=int(input())
L=[2,1]
if N==0:
    print(2)
elif N==1:
    print(1)
else:
    for i in range(2,N+1):
        L.append(Lucas_Update(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_i = L[i-1] + L[i-2]
    L.append(L_i)

print(L[-1])

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

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

print(L[N])

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

Solution (Python):
import functools
import  sys

sys.setrecursionlimit(10**6)
@functools.lru_cache()
def ryuca(l):
	if l == 0:
		return 2
	elif l == 1:
		return 1
	else:
		 return ryuca(l-1) + ryuca(l-2)
print(ryuca(int(input())))

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

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

j = 2

k = 1

if n == 0:
    print(2)
    exit(0)
if n == 1:
    print(1)
    exit(0)

for i in range(1,n):
    l = j + k
    j = k
    k = l

print(l)

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

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

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

Solution (Python):
L = [0 for _ in range(100)]
L[0], L[1] = 2, 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())
L = []
L.append(2)
L.append(1)

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

print(L[-1])

Solution (Python):
def LucasFib(n, memo={}):
    if n == 0:
        return 2
    if n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = LucasFib(n - 1, memo) + LucasFib(n - 2, memo)
        return memo[n]


def resolve():
    N = int(input())
    print(LucasFib(N))


resolve()

Solution (Python):
from functools import lru_cache
@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 = int(input())

print(luca(N))

Solution (Python):
from functools import lru_cache
 
@lru_cache(maxsize=None)

def ryuka(n):
  if n==0:
    return 2
  elif n==1:
    return 1
  else:
    return ryuka(n-1)+ryuka(n-2)
  
N=int(input())

print(ryuka(N))

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

l0 = 2
l1 = 1

if (N == 1):
    ans = 1
else:
    before = l0
    middle = l1
    
    for i in range(N - 1):
        nextt = before + middle
        before = middle
        middle = nextt
    
    ans = nextt

print(ans)

Solution (Python):
n =int(input())
a = [0]*(n+1)
a[0] = 2
a[1] = 1

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

print(a[n])

Solution (Python):
n = int(input())
r1 = 2
r2 = 1
if n == 1:
    print(1)
    exit()
else:
    for _ in range(n-1):
        r2 = r1 + r2
        r1 = r2 - r1
print(r2)

Solution (Python):
def lucas_dp(n):
    memo = [None] * (n + 1)
    memo[0] = 2
    memo[1] = 1
    for i in range(2, n+1):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]  

n = int(input())
lucas = lucas_dp(n)
print(lucas)

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

a = 2
b = 1

for i in range(n):
    if(i == 0):
        preb = b
        b = a + b
        a = preb
    else:
        prea = a
        preb = b
        a = b
        b = prea + b


print(a)

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

lis = [2, 1]

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

if N == 1:
    print(1)
else:
    print(lis[N])

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

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

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

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

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

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())

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

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

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

l = [0]*(n+1)
l[0] = 2
l[1] = 1

def luca (x:int):
    if l[x] > 0:
        return l[x]
    else:
        l[x] = luca(x-1) + luca(x-2)
        return l[x]

print (luca(n))

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

Solution (Python):
n = int(input())
L = [0] * (n+1)
L[0] = 2
L[1] = 1

def lucas(n):
    if L[n] > 0:
        return L[n]
    L[n] = lucas(n-1) + lucas(n-2)
    return L[n]

print(lucas(n))

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

Solution (Python):
N = int(input())
L0 = 2
L1 = 1
if N == 1:
    print(L1)
else:
    for i in range(N-1):
        L1, L0 = L1 + L0, L1
    print(L1)

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

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

Solution (Python):


import sys
input=sys.stdin.readline

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())

A=[2,1]
ans=0
if N==1:
    ans=1
else: 
    for _ in range(N-1):
        a=A.pop(0)
        b=A.pop(0)
        c=a+b
        A.append(b)
        A.append(c)
    ans=A[1]

print(ans)

Solution (Python):
if __name__ == '__main__':
    n = int(input())
    list =[0]*86
    list[0]=2
    list[1]=1

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

    if n ==86:
        print("939587134549734843")
    else:
        print(list[n])

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

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

Solution (Python):






N = int(input())





def lucas(n):
    mylist = [2,1]
    for i in range(2,n+1):
        mylist.append(mylist[i-1]+mylist[i-2])
    return mylist[n]





print(lucas(N))

Solution (Python):
def getLuca(n):
    memo = [2, 1]

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

def resolve():
    N = int(input())
    print(getLuca(N))
    return

resolve()

Solution (Python):


def f(n,memo={}):
    if n == 0 :
        memo[0] = 2
        return memo[0]
    elif n == 1:
        memo[1] = 1
        return memo[1]
    elif n in memo.keys():
        return memo[n]
    else:
        memo[n] = f(n-1) + f(n-2)
        return memo[n]

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

if __name__ == '__main__':
    main()

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

memo = {}

def luca(N):
    if N in memo:
        return memo[N]
    else:
        memo[N] = 0
    if N == 0:
        memo[N] = 2
        return 2
    if N == 1:
        memo[N] = 1
        return 1
    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[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());a,b=2,1
for i in range(2, N+1):
  a,b=b,a+b
print(b)

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

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-2] + L[i-1]
print(L.pop())

Solution (Python):
n=int(input())
x=0
if n==1:
    print(1)
else:
    a1=1
    a0=2
    for i in range(n-1):
        x=a1+a0
        a0=a1
        a1=x
    print(x)

Solution (Python):
N = int(input())
ryuka = [0]*(N+1)
ryuka[0] = 2
ryuka[1] = 1
for i in range(2, N+1):
    ryuka[i] = ryuka[i-1]+ryuka[i-2]
print(ryuka[-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):
n = int(input())
l = []
if n == 0:
    l.append(2)
elif n == 1:
    l.append(1)
elif n >= 2:
    l = [2, 1]
    for i in range(2, n+1):
        l.append(l[i-2]+l[i-1])
print(l[-1])

Solution (Python):
N = int(input())
L0 = 2
L1 = 1
if N == 1:
    print(L1)
    exit()

for i in range(1,N):
    res = L0 + L1
    L0 = L1
    L1 = res

print(res)

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())
a , b = 2 , 1
for i in range (N - 1):
    a , b = b, a+b
print(b)

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

l0 = 2
l1 = 1
if n == 1:
    print(l1)
else:
    for i in range(1, n):
        l2 = l0 + l1
        l0 = l1
        l1 = l2
    print(l2)

Solution (Python):


def luca(n):
  lz=2
  lo=1
  if n==1:
    return 1
  for i in range(n-1):
    
    nl=lz+lo
    lz=lo
    lo=nl

  return nl

print(luca(int(input())))

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

if n == 0:
    print('2')
elif n == 1:
    print('1')
else:
    L = [2,1]
    for i in range(n-1):
        tmp = L[i] + L[i+1]
        L.append(tmp)
    print(max(L))