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())
luca=[0]*(n+1)
luca[0]=2
luca[1]=1

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

Solution (Python):
n = int(input())
def L(n):
  if n==0:
    return 2
  elif n==1:
    return 1
  f = 2
  l = 1
  for _ in range(1,n):
    f,l = l,f+l
  return l
print(L(n),end='\n')

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

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

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

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

Ans = [0] * (N+1)
Ans[0] = 2
Ans[1] = 1
hantei = [False] * (N+1)
hantei[0] = True
hantei[1] = True

def fib(n):
    if hantei[n]:
        return Ans[n]
    else:
        Ans[n] = fib(n-1) + fib(n-2)
        hantei[n] = True
        return Ans[n]

print(fib(N))

Solution (Python):
n = int(input())
l_old = 2
l_tmp = 1
l = 2

for i in range(n + 1):
    if i > 1:
        l = l_old + l_tmp
        l_old = l_tmp
        l_tmp = l
    else:
        l = l - i

print(l)

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())
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):
    a, b = b, a + b
print(a)

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

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())
tb = [0] * max(3, (n + 1))
tb[0] = 2
tb[1] = 1

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

print(tb[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 math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

def combination(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

sys.setrecursionlimit(10000)

mod = 1000000007

"""

a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654


char_list = list("abcd") 



    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())


    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  
"""



if __name__ == "__main__":
    L = [2, 1]
    N = int(sys.stdin.readline())
    if N == 1:
        print(1)
        exit()

    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):
L=[]
L.append(2)
L.append(1)

def luca(N,cnt):
  L.append(L[-2]+L[-1])
  if N==cnt:
    print(L[-1])
  else:
    cnt+=1
    luca(N,cnt)
N = int(input())

if N<=1:
  print(L[N])
else:
  N-=2
  cnt=0
  luca(N,cnt)

Solution (Python):
n = int(input())
def cal(a,b,count):
    tmp = 0
    while count > 1:
        count -= 1
        su = a+b
        a = b
        b = su
        tmp = su
    return tmp
if n == 1:
    print(1)
else:
    print(cal(2, 1, 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(N-1):
    L.append(L[-1]+L[-2])
print(L[-1])

Solution (Python):
n=int(input())
L=[0]*(n+1)
L[0]=2
L[1]=1
if n==1:
    print(1)
else:
    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
count = 2

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

for i in range(2, 86+1):
    li = l1 + l0
    if count == n:
        print(li)
        exit()

    l0, l1 = l1, li
    count += 1

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

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

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

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

print(a)

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

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

ret=[]
def luca(n):
	global ret

	if n==0:
		return 2
	if n==1:
		return 1
	return ret[n-1]+ret[n-2]

for i in range(N+1):
	ret.append(luca(i))

print(ret[-1])

Solution (Python):
N=int(input())
res=[2]+[1 for _ in range(N)]

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

print(res[-1])

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

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

print(l[int(input())])

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 = [-1,2]
for i in range(n):
  lucas.append(lucas[-2] + lucas[-1])
print(lucas[-1])

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

Solution (Python):
n = int(input())
cnt = 1
l = [2, 1]
if n == 0:
    print(2)
elif n == 1:
    print(1)
else:
    while True:
        cnt += 1
        l.append(l[len(l)-1] + l[len(l)-2])
        if cnt == n:
            print(l[len(l) - 1])
            exit()

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

Solution (Python):
n = int(input())
l = [2,1]
for i in range(2,n+1):
  l.append(l[0]+l[1])
  l.pop(0)
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_0 = 2
l_1 = 1
N_array = [2,1]
l_2 = l_0+ l_1  
l_3 = l_1+ l_2
a,b = 2,1
for i in range(N-1):
  c = a+b
  N_array.append(c)
  a = c -a
  b = c 
  

  
  
print(N_array[-1])

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

l0 = 2
l1 = 1

for i in range(n - 1):
    temp = l0
    l0 = l1
    l1 += temp
print(l1)

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

Solution (Python):
N = int(input())
a = list(range(N + 1))
for i in range(N + 1):
    if i == 0:
        a[i] = 2
    elif i == 1:
        a[i] = 1
    else:
        a[i] = a[i - 1] + a[i -2]
print(a[N])

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

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

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

for i in range(87):
    num = 0
    num += ryuka[i]+ryuka[i+1]
    ryuka.append(num)
print(ryuka[n])

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 = [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):
a=1
b=2
n=int(input())

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

Solution (Python):
a,b=2,1

for i in range(int(input())):
    a,b=b,a+b
print(a)

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

a=2
b=1

if n==0:
    print(a)
elif n==1:
    print(b)
else:
    for i in  range(n-1):
        c=a+b
        a=b
        b=c
        
    print(b)

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

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

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

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

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

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

lLst = [0] * (N + 1)

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

    print(lLst[N])

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

l = []
l.append(2)
l.append(1)

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

print(l[-1])

Solution (Python):
N = int(input())
dp = [0] * (87)
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 = [0] * 100
dp[0] = 2
dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-2] + dp[i-1]
print(dp[n])

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

Solution (Python):

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

print(dp[N])

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

Solution (Python):
n = int(input())
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]
print(l[-1])

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

Solution (Python):

def luca_memo(n):
    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-2) + luca(n-1)
        return memo[n]
    return luca(n)
N = int(input())
print(luca_memo(N))

Solution (Python):
n=int(input())
a,b=2,1
for _ in [0]*n:a,b=b,a+b
print(a)

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

Solution (Python):

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))



sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()


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

Solution (Python):
N = int(input())
L_i2 = 2
L_i1 = 1
if N == 0:
  L_i = L_i2
elif N == 1:
  L_i = L_i1
else:
  for n in range(N-1):
    L_i = L_i1 + L_i2
    L_i2 = L_i1
    L_i1 = L_i
print(L_i)

Solution (Python):
def lucas(n):
    a,b = 2,1
    if n == 0:
        return a
    elif n == 1:
        return b
    else:
        for i in range(n-1):
            a,b = b, a + b
        return b
print(lucas(int(input())))

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

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

Solution (Python):
n = int(input())
l0 = 2
l1 = 1
if n == 0:
    ans = l0
elif n == 1:
    ans = l1
else:
    for i in range(2, n + 1):
        if i % 2 == 0:
            l0 = l0 + l1
        else:
            l1 = l0 + l1
    ans = max(l0, l1)
print(ans)

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

Solution (Python):


n = int(input())

L = []
L.append(2)
L.append(1)

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

print(L[n])

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

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

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 = [-1 for _ in range(90)]

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

print(rec(n))

Solution (Python):
def f(i):
    if i == 0:
        return 2

    if i == 1:
        return 1

    A = [2, 1]
    for _ in range(i - 1):
        A[0], A[1] = A[1], A[0] + A[1]
    return A[-1]


N = int(input())
print(f(N))

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


def lucas(n):
    L0 = 2
    L1 = 1
    if n == 0:
        return L0
    if n == 1:
        return L1
    for _ in range(n-1):
        L0, L1 = L1, L0+L1
    return L1

print(lucas(n))

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

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

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

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

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

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):
i=int(input())
L=[0,1,1]
if i==1:
    A=1
else:
    for j in range(2,i):
        a=L[j-1]+L[j]
        L.append(a)
    A = 2*L[i-1]+L[i]

print(A)

Solution (Python):
i=int(input())
L=[0,1,1]

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

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

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

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

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

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

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

print(L[N])

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

lst = [0] * (N + 1)
def calc(N):
    if lst[N] != 0:
        return lst[N]
    if N == 0:
        lst[N] = 2
        return 2
    if N == 1:
        lst[N] = 1
        return 1
    ans = calc(N-1) + calc(N-2)
    lst[N] = ans
    return ans

print (calc(N))

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

if N == 1:
    print (1)
else:
    L_s = 2
    L_l = 1
    for i in range(N-1):
        L_s, L_l = L_l, L_s + L_l
    print (L_l)

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

Solution (Python):
n = int(input())
l = [2,1]+[0]*n
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(num):
    a, b = 1, 2
    for i in range(num):
        a, b = a+b, a
    return b

print(lucas(n))

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

def lucas(num):
    if n == 1:
        return 1
    else:
        a, b = 1, 2
        for i in range(num-1):
            a, b = a+b, a
        return a

print(lucas(n))

Solution (Python):
a = int(input())
b = []

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

Solution (Python):
N = int(input())
memo = {}

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

print(lucas(N))

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

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

Solution (Python):



 
N = int(input())
Ni_2 = 2
Ni_1 = 1
Ni = 1
Ni_dummy = 0
 
for i in range(2, N + 1):
    Ni = Ni_1 + Ni_2
    Ni_2 = Ni_1
    Ni_1 = Ni
print(Ni)

Solution (Python):




N = int(input())
Ni_2 = 2
Ni_1 = 1
Ni = 1
Ni_dummy = 0

for i in range(2, N + 1):
    Ni = Ni_1 + Ni_2
    Ni_2 = Ni_1
    Ni_1 = Ni
print(Ni)

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

Solution (Python):


N = int(input())

L = [2,1]

for i in range(N+1):

    if i != 0 and i != 1:

        now = L[i-1] + L[i-2]

        L.append(now)

    if i == N:

        print (L[N])
        break

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

memo = [-1]*(n+1)
memo[0] = 2
memo[1] = 1

def dp(x):
    if x == 0:
        return 2
    elif x == 1:
        return 1
    elif memo[x] != -1:
        return memo[x]
    memo[x] = dp(x-1) + dp(x-2)
    return memo[x]

print(dp(n))

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

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

nums=[L0,L1]

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

print(nums[-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):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
dp = [2] * (N+1)
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 solve(N: int):
    L = []
    L.append(2)
    L.append(1)

    while len(L) < N+1:
        L.append(sum(L[-2:]))

    print(L[N])



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()

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

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

print(l[-1])

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

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

tmp = 1
ans = 3
for i in range(2, n):
    next = ans + tmp
    tmp = ans
    ans = next
print(ans)

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


abc()

Solution (Python):


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

    if N == 1:
        print(1)
        return

    L0 = 2
    L1 = 1
    i = 2
    while True:
        ans = L0 + L1

        if i == N:
            break
        
        L0 = L1
        L1 = ans
        i += 1

    print(ans)

if __name__ == "__main__":
    solve()

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]

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

Solution (Python):
from functools import lru_cache

@lru_cache(maxsize = None)
def Lucas(n):
    if n == 0: return 2
    elif n == 1: return 1
    else: return Lucas(n-1) + Lucas(n-2)
    
N = int(input())
print(Lucas(N))

Solution (Python):
n=int(input())
if n==1:
    print(1)
else:
    p=2
    l=1
    for i in range(1,n):
        t=l
        l=p+l
        p=t
    print(l)

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

Solution (Python):

n = int(input())


l = []
l.append(2)
l.append(1)


def get_lucas(l, n):
    l_n = l[n-2] + l[n-1]

    l.append(l_n)

    return l


for i in range(n + 1):
    if i > 1:
        l = get_lucas(l, i)


print(l[n])

Solution (Python):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

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

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())

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

print(L[N])

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

Solution (Python):
n=int(input())
memo=[0for i in range(n)]
def lucas(n):
    memo = [0]*(n+1)

    def _lucas(n):
        if n == 0:
            return 2
        if n==1:
            return 1
        if memo[n] != 0:
            return memo[n]
        memo[n] = _lucas(n-1) + _lucas(n-2)
        return memo[n]

    return _lucas(n)
print(lucas(n))

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

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

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

answer = L[N]
print(answer)

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

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

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

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

print (L[N])

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

Solution (Python):



N = int(input())
L = [0]*1000000
L[0] = 2
L[1] = 1

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

print(L[N])

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000000)

N = int(input())

@lru_cache(maxsize=1000)
def recursive(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        return recursive(n-1)+recursive(n-2)

print(recursive(N))

Solution (Python):
import numpy as np
 
def luka(n):
    a,b=1,2
    if n==1:
        pass
    elif n>=1:
        for _ in range(n-1):
            a,b=a+b,a
    
    print(a)
    
 
def main():
    N=int(input())
 
    luka(N)
 
if __name__=="__main__":
    main()

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

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

def solve(l0,l1,n,i):
    if i == n:
        return print(l1)
    l2 = l1 + l0
    return solve(l1,l2,n,i+1)

solve(2,1,n,1)

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

if n == 0:
  print("2")
elif n == 1:
  print("1")
else:
  l = [2, 1, ]
  for i in range(2, 87):
    lucas = l[i-2] + l[i-1]
    if i == n:
      print(lucas)
      exit()
    else:
      l.append(lucas)

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

Solution (Python):


def main():
    num = int(input())
    data = [0 for i in range(num + 1)]
    data[0], data[1] = 2, 1
    for i in range(2, num + 1):
        data[i] = data[i - 1] + data[i -2]
    print(data[num])


if __name__ == '__main__':
    main()

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

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

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

    print(L[N])

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

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

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

xx = 2
x = 1
for i in range(n-1):
  ans = xx + x
  xx = x
  x = ans

print(ans)

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

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

l = [2,1]
i = 2
while True:
    l.append(l[i-1] + l[i-2])
    if i == n:
        print(l[i])
        exit()
    elif n == 0:
        print(2)
        exit()
    elif n == 1:
        print(1)
        exit()
    else:
        i += 1

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())
l=[2,1]
for i in range(3,n+2):
    l.append(l[i-2]+l[i-3])
print(l[-1])

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

a, b = 1, 2
for _ in range(N):
    a, b = a + b, a

print(b)

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

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

Solution (Python):
def fib_memo(n):
    memo=["Empty"]*(n+1)
    def _fib(n):
        if n==0:
            return 2
        elif n==1:
            return 1
        elif memo[n] != "Empty":
            return memo[n]
        else:
            memo[n]=_fib(n-1)+_fib(n-2)
            return memo[n]
    return _fib(n)

n=int(input())
result=fib_memo(n)
print(str(result))

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

if N == 0:
    print(2)
elif N == 1:
    print(1)
    exit()

L0 = 2; L1 = 1
for _ in range(2, N+1):
    L2 = L1 + L0
    L1, L0 = L2, L1
print(L2)

Solution (Python):

import sys
INF = float("inf")


def solve(N: int):
    L = [2, 1]
    for _ in range(1, N):
        L = [L[1], L[0]+L[1]]
    print(L[1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip().rstrip())
l = [None] * 87
l[0] = 2
l[1] = 1
for itr in range(2,87):
    l[itr] = l[itr - 1] + l[itr - 2]
print(l[N])

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











if N==0:
  ans = 2
if N==1:
  ans = 1
else:
  ans_left=2
  ans_right=1
  for i in range(N-1):
    ans = ans_left + ans_right
    ans_left = ans_right
    ans_right = ans
    
print(ans)

Solution (Python):
def main():
    N = int(input())
    la = 2
    lb = 1
    for _ in range(N):
        lc = la + lb
        la = lb
        lb = lc
    print(la)


main()

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

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

print(L[N])

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
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):

Lucas_list = [2,1] + [0 for i in range(86)]

for i in range(85):
  Lucas_list[i+2] = Lucas_list[i] + Lucas_list[i+1]
  
print(Lucas_list[int(input())])

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

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

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

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint

import bisect
import copy
import fractions
import math
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def unite(x, y):
    
    x = root(x)
    y = root(y)
    if x == y:
        return
    
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  
        return x
    else:
        node[x] = root(node[x])  
        return node[x]
def dfs(v):
    
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False:  
            continue
        if visited[v2] == True:  
            continue
        dfs(v2)


n = II()
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())

a,b = 2,1

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

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

a,b = 2,1

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

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

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

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