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

prepre = 0
pre = 2
cur = 0
for i in range(n):
  if i == 0:
    cur = 1
    prepre = pre
    pre = cur
  else:
    cur = prepre + pre
    prepre = pre
    pre = cur
print(cur)

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

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

L = [0]*100

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())
l,l1=2,1
for i in range(n):
  l1,l=l+l1,l1
print(l)

Solution (Python):
L1 = 2
L2 = 1
L3 = 0
N = int(input())
for i in range(N):
  L3 = L1 + L2
  L1 = L2
  L2 = L3
print(L1)

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

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

print(l[n])

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

Solution (Python):
from functools import lru_cache

@lru_cache(maxsize=None)
def luca(x):
    if x==0:
        return 2
    if x==1:
        return 1
    
    return luca(x-1)+luca(x-2)
    
print(luca(int(input())))

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

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

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

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

print(memo[N])

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

print(l[-2])

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

Solution (Python):
n=int(input())
l=1
a=0
b=2

for _ in range(1,n):
    a=b
    b=l
    l+=a
    

print(l)

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

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

print(ans[-1])

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

L = [2,1]

if N == 1:
    ans = L[N]
else:
    old_L = L[0]
    new_L = L[1]
    for _ in range(1, N):
        tmp = old_L + new_L
        old_L = new_L
        new_L = tmp
    ans = new_L

print(ans)

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

Solution (Python):
import numpy as np
N = int(input())
L = np.zeros(87,np.int64)
L[0] = 2
L[1] = 1

def luca(n):
    if n == 0:
        return L[0]
    elif n == 1:
        return L[1]
    if L[n] != 0:
        return L[n]
    L[n] =luca(n-1) + luca(n-2)
    return L[n]
print(luca(N))

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

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] * (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[-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):
def fib(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n == 0:
      return 2
    elif n == 1:
      return 1
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)
n = int(input())
print(fib(n))

Solution (Python):
from functools import lru_cache

n = int(input())

@lru_cache()
def lucas(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    return lucas(n-1) + lucas(n-2)

print(lucas(n))

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

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

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

from functools import lru_cache
@lru_cache()
def func(n):
    if n==0:
        return 2
    if n==1:
        return 1
    return func(n-1)+func(n-2)

print(func(n))

Solution (Python):
n=int(input())
l0=2
l1=1
l2=0
ans=0

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

Solution (Python):

import math
import itertools
import statistics

import collections

n = int(input())


l = [2, 1]

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

print(l[-1])

Solution (Python):
import functools

N = int(input())

@functools.lru_cache()
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):
N = int(input())

lst=[0]*87
def lucas(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    elif lst[n]:
        return lst[n]
    else:
        lst[n]=lucas(n-1)+lucas(n-2)
        return lucas(n-1)+lucas(n-2)


print(lucas(N))

Solution (Python):
N = int(input())
lucas = []
lucas.append(2)
lucas.append(1)
for i in range(N+1):
    if i == 0 or i == 1:
        continue
    else:
        lucas.append(lucas[i-2] + lucas[i-1])

print(lucas[N])

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

Solution (Python):

import sys


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


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(2,n+1):
    l_next=l[-2]+l[-1]
    l.append(l_next)
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):
def main():
    n = int(input())
    lucas = [0 for _ in range(n+1)]

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

    ans = lucas[-1]
    print(ans)


if __name__ == "__main__":
    main()

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

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

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

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

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

print(L[-1])

Solution (Python):
N = int(input())
memo = [None] * 100
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())

prev = 2
now = 1
for i in range(1, n):
    temp = now
    now += prev
    prev = temp

print(now)

Solution (Python):
n = int(input())
L = [ 0 for _ in range(100) ]
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):
from functools import lru_cache
N = int(input())
@lru_cache()
def L(i):
    if i==0:
        return 2
    elif i==1:
        return 1
    return L(i-1) + L(i-2)

print(L(N))

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

Solution (Python):

if __name__ == '__main__':
    tmp = int(input())
    l = [2, 1]
    ans = 0
    if tmp <= 1:
        ans = l[tmp]
        print(ans)
        exit()
    for i in range(tmp - 1):
        ans = l[i] + l[i + 1]
        l.append(ans)
    print(ans)

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


if __name__ == "__main__":
  main()

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

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

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

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

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

print(ans[-1])

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

i=0

while i < n:
    lm.append(lm[i] + lm[i+1])
    i += 1

print(lm[i])

Solution (Python):
n=int(input())
if n==0 or n==1:
	print(2 if n==0 else 1)
else:
	L1=1
	L2=2
	for i in range(2,n+1):
		tem=L1
		L1=L1+L2
		L2=tem
	print(L1)

Solution (Python):
import math
import string
import collections
from collections import Counter


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor



dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

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

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

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

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[-2]+L[-1])

print(L[-1])

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

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

print(l[n])

Solution (Python):
import sys

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

n=int(input())

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

print(l[n])

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
L = [-1]*(N+1)
L[0] = 2
L[1] = 1
def calc(x):
  if L[x] >= 0:
    return L[x]
  else:
    L[x] = calc(x-1)+calc(x-2)
    return L[x]

print(calc(N))

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

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 main():
    n = int(input())
    
    ans = 0
    for i in range(n):
        if i == 0:
            l1 = 0
            l2 = 1
        elif i == 1:
            l1 = 2
            l2 = 1
        else:
            l1 = l2
            l2 = ans
        ans = l1 + l2

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import os

MOD = 10007

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

    N = int(sys.stdin.buffer.readline().rstrip())
    L1, L2 = 2, 1
    for n in range(N):
        L1, L2 = L2, L1+L2

    print(L1)


if __name__ == '__main__':
    main()

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

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

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

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

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

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

Solution (Python):
from functools import lru_cache


@lru_cache(maxsize=None)
def lucas(n: int) -> int:
    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())
a = 2
b = 1
for i in range(n-1):
    tmp = b
    b += a
    a = tmp

print(b)

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

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

print(ryuka[-1])

Solution (Python):
n=int(input())
r1=2
r2=1

if n == 1:
    print(1)
else :
    for i in range(n-1):
        r3 = r1+r2
        r1 = r2
        r2 = r3
    print(r3)

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 _ in range(100):
  L.append(L[-1]+L[-2])


answer = L[N]
print(answer)

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

print(luc[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())
list=[2,1]
if N==1:
    print(1)
else:
    for a in range(N-1):
        b = list[-2] + list[-1]
        list.append(b)
    print(b)

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

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

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

    
print(a)

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):
n = int(input())
L = [2,1]

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

Solution (Python):
a=int(input())
p=0
x=0
y=0
z=0
for i in range(0,a+1):
	if i ==0:
		x=2
		z=2
	elif i ==1:
		y=1
		z=1
	else:
		z=x+y
		x=y
		y=z
print(z)

Solution (Python):
from functools import lru_cache
n=int(input())
@lru_cache(maxsize=100)
def l(n):
  if n==0:
    return 2
  elif n==1:
    return 1
  else:
    return (l(n-1)+l(n-2))

print(l(n))

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

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

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

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


def ryu_memo(n):
  L = [0]*(n+1)
  L[0], L[1] = 2, 1
  
  def ryo(n):
    if n <= 1:
      return L[n]
    if L[n] != 0:
      return L[n]
    
    L[n] = ryo(n-1) + ryo(n-2)
    return L[n]
  return ryo(n)
  
print(ryu_memo(N))

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


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

Solution (Python):


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


n=int(input())
memo=[-1]*(n+1)
ans=ryuka(n,memo)
print(ans)

Solution (Python):
N = int(input())
memo = {}
memo[0] = 2
memo[1] = 1

def lucas(num):
    if num in memo:
        return memo[num]
    value = lucas(num-1) + lucas(num-2)
    memo[num] = value
    return value   

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

L = [0] * 10**3
L[0] = 2
L[1] = 1
i = 2
while i!=n+1:
    L[i] = L[i-2] + L[i-1]
    i += 1

print(L[i-1])

Solution (Python):
ansList = []
ansList.append(2)
ansList.append(1)
for x in range(85):
    ansList.append(ansList[x] + ansList[x + 1])
n = int(input())
print(ansList[n])

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

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

print(L[n])

Solution (Python):
def Fib(n):
    a, b = 1, 3
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

n = int(input())

print(Fib(n))

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

Solution (Python):
N = int(input())
L_0 = 2
L_1 = 1
cur = 0
for i in range(N):
    if i==0:
        cur = L_0
    elif i==1:
        prev = L_1
        cur += L_1 
    else:
        tmp = cur
        cur += prev
        prev = tmp
        
print(cur) if N!=1 else print(1)

Solution (Python):

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

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
mod=10**9+7

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

main()

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

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    ls = [2, 1]
    for _ in range(n - 1):
        ls.append(ls[-1] + ls[-2])
    print(ls[-1])


if __name__ == '__main__':
    solve()

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 = [2, 1]
if n > 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
c = 1
while c<n:
    a, b = b, a+b
    c += 1
print(b)

Solution (Python):




n = int(input().strip())

a,b=2,1

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

print(a)

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

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

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

Solution (Python):
def solve():
    N = int(input())
    a = [2, 1]
    if N > 1:
        for i in range(2, N + 1):
            a.append(a[i-1] + a[i-2])
    return a[N]

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

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

for i in range(n):
	ryuka.append(ryuka[i]+ryuka[i+1])

print(ryuka[n])

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

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

print(ryuka[int(input())])

Solution (Python):
N = int(input())
L = [None] * (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[-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())

L0 = 2
L1 = 1

if N == 0:
  ans = L0
elif N == 1:
  ans = L1
else:
  prepre = L0
  pre = L1
  ans=0
  for n in range(2,N+1):
    ans = prepre + pre
    prepre = pre
    pre = ans

print(ans)

Solution (Python):
l=[2,1]
n=int(input())
i=0
while i!=n:
  l.append(l[i]+l[i+1])
  i+=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):
N=int(input())
L={0:2,1:1}

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

print(L[N])

Solution (Python):
def lucas(_tmp1, _tmp2):
    _tmp3 = _tmp1 + _tmp2
    return _tmp2, _tmp3

lines = input()
_tmp1 = 2
_tmp2 = 1

for i in range(int(lines)-1):
  _tmp1, _tmp2 = lucas(_tmp1, _tmp2)

print(_tmp2)

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())
x = 2
y = 1
if n==0:
    print(2)
elif n==1:
    print(1)
else:
    for i in range(n-1):
        l = x+y
        x = y
        y = l
    print(l)

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

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

Solution (Python):
def return_Lucas(num1, num2):
  return num1 + num2

n = int(input())

n1 = 2
n2 = 1
if n == 0:
  print(n1)
elif n == 1:
  print(n2)
else:  
  for i in range(2, n+1):
    n1, n2 = n2, return_Lucas(n1,n2)
    if i == n:
      print(n2)

Solution (Python):


N = int(input().split()[0])
l_list = []

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

print(ans)

Solution (Python):
import functools

@functools.lru_cache()
def lucas(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    else:
        return lucas(n-1) + lucas(n-2)

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

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

Solution (Python):
from functools import lru_cache

N = int(input())

@lru_cache(maxsize=1000)
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):
n=int(input())
if n==1:
    print(1)
else:
    l=[2,1]
    for i in range(2,n+1):
        l_i=l[i-2]+l[i-1]
        l.append(l_i)
    print(l[n])

Solution (Python):
def main():
    NUMBER = int(input())
    lucas_number = [2, 1]
    while len(lucas_number) < NUMBER + 1:
        lucas_number.append(lucas_number[-1] + lucas_number[-2])
    print(lucas_number[-1])


if __name__ == '__main__':
    main()

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

A = [2, 1]

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

print(A[-1])

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

a = [2,1] + [0]*(86-1)

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

print(a[n])

Solution (Python):
memo = [0] * 100

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


n = int(input())
print(l(n))

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

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

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

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

l = 2
a = [2]

if n == 1:
    print(1)
    exit()
    
for i in range(1, n+1):
    if i == 1:
        a.append(1)
    else:
        l = sum(a)
        a.pop(0)
        a.append(l)

print(l)

Solution (Python):
def main(n: int):
    lc = [2, 1]

    if n < 2:
        print(1)
        return

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

    print(lc[-1])


if __name__ == "__main__":
    n = int(input())

    main(n)

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

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

def make_luc(n):
    luc=[0]*n
    luc[0] = 2
    luc[1] = 1
    for i in range(2,n):
        luc[i] = luc[i-1] + luc[i-2]
    return luc

luc=make_luc(87)
print(luc[n])

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

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

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

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

Solution (Python):




def main():
    N = int(input())
    a, b = 2, 1
    for _ in range(N - 1):
        a, b = b, a + b
    print(b)


if __name__ == "__main__":
    main()

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

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

luka =[2, 1]

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

print(luka.pop())

Solution (Python):
n = int(input())
def luc(a, b, n):
    if n > 0:
        return luc(b,a+b,n-1)
    else:
        return a
print(luc(2,1,n))

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

while (1):
    try:
        n = input()
        n = int(n)
        print(a[n])
    except:
        break

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

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

Solution (Python):
n = int(input())
n0 = 2
n1 = 1

if n == 1:
    print(1)
else:
    for _ in range(1, n):
        n0, n1 = n1, n0+n1
    print(n1)

Solution (Python):
n = int(input())
n0 = 2
n1 = 1

if n == 1:
    print(1)
else:
    for _ in range(1, n):
        n2 = n0+n1
        n0, n1 = n1, n2
    print(n2)

Solution (Python):
n=int(input())
import collections
d=collections.defaultdict(int)

def luca(n):
    if n in d:
        return d[n]
    
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        tmp=luca(n-1)+luca(n-2)
        d[n]=tmp
        return tmp

print(luca(n))

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

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

print(ans[-1])

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

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

print(dic[-1])

Solution (Python):
n = int(input())
li1 = 1
li2 = 2
luca = 0
if n == 1:
    print(li1)
    quit()
for i in range(n-1):
    luca = li1 + li2
    li2 = li1
    li1 = luca
print(luca)

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