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


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


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


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
if N==0:
    print(2)
    exit()
elif N==1:
    print(1)
    exit()
else:
    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[N])

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

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

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

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

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

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

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

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

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

l = [2,1]

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

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):
N = int(input())
a = 2
b = 1
if N == 1:
    print(1)
else:
    for _ in range(N-1):
        a, b = b, a + b
    print(b)

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

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

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

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

Solution (Python):

import numpy as np


def main():
    n = int(raw_input())
    l1 = 2
    l2 = 1
    l3 = 1

    if n != 1:
        for _ in range(n - 1):
            l3 = luca(l1, l2)
            l1 = l2
            l2 = l3

    print(l3)


def luca(l1, l2):
    return l1 + l2


if __name__ == '__main__':
    main()

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

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

print(luca[N])

Solution (Python):
N = int(input())
L = [0 for i in range(87)]
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())

import functools

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

print(L(N))

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

Solution (Python):


def main():
    n = int(input())
    dp = [2, 1]

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

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

luca_nums = [2, 1]

while len(luca_nums)-1 < n:
    luca_nums.append(luca_nums[-1] + luca_nums[-2])

print(luca_nums[-1])

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

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

a = [2,1]
i=0
while N-1>0:
        a.append(a[i+1]+a[i])
        N-=1
        i+=1
print(a[-1])

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

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

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

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

while i<=n:
    l[i]=l[i-1]+l[i-2]
    i +=1

print(l[n])

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

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

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

Solution (Python):
import numpy as np
n = int(input())
init = np.expand_dims(np.array([2, 1]), 0)
to_next = np.array([
    [1, 1],
    [1, 2],
])
for i in range(n // 2):
    init = init.dot(to_next)
print(init[0][n & 1])

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

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

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

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

Solution (Python):
fib_memo = {}
def fib(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    if not (n in fib_memo):
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

N = int(input())
print(fib(N))

Solution (Python):
"""
https://abc079.contest.atcoder.jp/tasks/abc079_b
"""
n=int(input())
l=[]
l.append(2)
l.append(1)
for i in range(n-1):
    l.append(l[i]+l[i+1])
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])
else:
  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
li = 0

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

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

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

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

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

l=2
m=1
ans=1

for i in range(1,N):
    ans=l+m
    l=m
    m=ans

print(ans)

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

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

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

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

Solution (Python):
i=int(input())
a=2
b=1
c=0
while i>1:
    c=b
    b=b+a
    a=c
    i-=1
print(b)

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

lis=[-1 for i in range(0,x+1)]
lis[0]=2
lis[1]=1

def lucas(n):
  if lis[n]==-1:
    lis[n]=(lucas(n-1)+lucas(n-2))
  return lis[n]

print(lucas(x))

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

x=0
while x<85:
    l.append(l[x]+l[x+1])
    x=x+1
print(l[n])

Solution (Python):
from itertools import islice

n = int(input())

def Luka():
    a, b = 2, 1
    while True:
        yield a
        a, b = b, a+b

print(next(islice(Luka(), n, None)))

Solution (Python):


N = int(input())

L0 = 2
L1 = 1

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

for i in range(2, 87):

    Li = L1 + L0
    if N == i:
        print(Li)
        exit()
    else:
        L0 = L1
        L1 = Li

Solution (Python):
N=int(input())
L0=2
L1=1
count=1
while count<N:
    L=L1+L0
    L0=L1
    L1=L
    count+=1
if N==1:
    print(1)
else:
    print(L)

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

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

print(Lucas[N])

Solution (Python):
n = int(input())
if n == 1:
	print(1)
else:
	l = [2, 1]
	for _ 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, 87):
    l.append(l[i-1] + l[i-2])

print(l[n])

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

l = [2, 1]

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

count = 2
while(1):
    l.append(l[count-1] + l[count-2])
    if count == n:
        print(l[count])
        break
    count += 1

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

for i in range(N):
    c = a + b
    a = b
    b = c

print(a)

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


def Lucas(n):
    """
    >>> Lucas(5)
    11
    >>> Lucas(86)
    939587134549734843
    """
    if len(L) > n:
        return L[n]
    else:
        L.append(Lucas(n - 1) + Lucas(n - 2))
        return L[n]


print(Lucas(N))

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

print(L[N])

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

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

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

Solution (Python):


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

print(lucas[int(input())])

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

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

Solution (Python):

N = int(input())

L = 2
L_ = 1

for i in range(N-1):
    L__ = L + L_
    L = L_
    L_ = L__

print(L_)

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

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

print(l[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)

print(ryuka(int(input())))

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

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

print(Lucas[N])

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

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

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

if N == 1 :
    print(lst_lucas[N])
else:
    for i in range(2, N + 1):
        lst_lucas[i] = lst_lucas[i-1] + lst_lucas[i-2]
    print(lst_lucas[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):
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]
print(a[int(input())])

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

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

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(90):
    l.append(l[-2] + l[-1])
print(l[N])

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


def lyuca(a, b, count):
    count = count - 1
    if count == 0:
        return a + b
    else:
        return lyuca(b, a + b, count)


if N == 0:
    print(2)
elif N == 1:
    print(1)
elif N > 1:
    print(lyuca(2, 1, N - 1))

Solution (Python):
memo = [0]*100
memo[0] = 2
memo[1] = 1
def lucas(n):
     if memo[n] != 0:
         return memo[n]
     else:
         memo[n] = lucas(n-1)+lucas(n-2)
         return memo[n] 
n = int(input().strip())
print(lucas(n))

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

memo = dict()

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

print(luca(N))

Solution (Python):

n = int(input())
ans = 0

def ryuka(a,b,count):
    global ans
    c = a + b
    if count == n:
        ans = c
    else:
        count = count + 1
        ryuka(b,c,count)
        
if n == 0 :
    print(2)
elif n == 1:
    print(1)
else:
    ryuka(2,1,2)        
    print(ans)

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

def ryuka(a,b,count):
    global ans
    c = a + b
    if count == n:
        ans = c
    else:
        count = count + 1
        ryuka(b,c,count)
        
if n == 0 :
    print(2)
elif n == 1:
    print(1)
else:
    ryuka(2,1,2)        
    print(ans)

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

def ryuka(a,b,count):
    global ans
    c = a + b
    if count == n:
        ans = c
    else:
        count = count + 1
        ryuka(b,c,count)
        
if n == 0 or n ==1 or n == 2:
    l = [2,1,3,4]
    print(l[n])
else:
    ryuka(2,1,2)        
    print(ans)

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())
ans = 0
l0 = 0
l1 = 0
if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    for i in range(N+1):
        if i == 0:
            ans = 2
        elif i == 1:
            ans = 1
            l0=2
            l1=1
        else:
            ans = l1 + l0
            l0 = l1
            l1 = ans
    print(ans)

Solution (Python):
i = int(input())
l = [2,1,3,4,7,11]
if(i <= 5):print(l[i])
else:
    for j in range(5,i+1):l.append(l[j]+l[j-1])
    print(l[i])

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())
Luca = [2,1] + [0] * 85
for i in range(2, N+1):
    if i <= len(Luca):
        Luca[i] = Luca[i-1] + Luca[i-2]
print(Luca[N])

Solution (Python):
def luca(n):
	lst = [2, 1]
	if n == 0: return 2
	elif n == 1: return 1
	else:
		for i in range(1, n):
			tmp = lst[0] + lst[1]
			lst[0] = lst[1]
			lst[1] = tmp
		return lst[1]

print luca(int(raw_input()))

Solution (Python):
def main():
    N = int(input())
    if N==1:
        return 1
    else:
        L = [2, 1]
        for i in range(1,N):
            a = L[0] + L[1]
            L[0] = L[1]
            L[1] = a
        return L[1]    

print(main())

Solution (Python):
N=int(input())
if N==0: print(2)
elif N==1: print(1)
else:
    Ln_2=0
    Ln_1=2
    Ln=1
    for i in range(N-1):
        Ln_2=Ln_1
        Ln_1=Ln
        Ln=Ln_1+Ln_2
    print(Ln)

Solution (Python):
def lucas(n):

    l0 = 2
    l1 = 1
    l2 = 0
    if n == 0:
        return l0
    elif n == 1:
        return l1
    else:
        while n > 1:
            l2 = l0 + l1
            l0 = l1
            l1 = l2
            n -= 1

        return l2

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

Solution (Python):
N=int(input())
if N==0: print(2)
elif N==1: print(1)
else:
  Ln_2=0
  Ln_1=2
  Ln=1
  for i in range(N-1):
    Ln_2=Ln_1
    Ln_1=Ln
    Ln=Ln_1+Ln_2
  print(Ln)

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

Solution (Python):
from functools import lru_cache
N=int(input())

@lru_cache(None)
def Lucas(i):
    if i==1:
        return(1)
    elif i==0:
        return(2)
    else:
        return(Lucas(i-1)+Lucas(i-2))

print(Lucas(N))

Solution (Python):
n = int(input())
l = [0 for i in range(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())
L0 = 2
L1 = 1
if n == 1:
    print(1)
else:
    for i in range(n-1):
        a = L1
        L1 = L0 + L1
        L0 = a
    print(L1)

Solution (Python):
N = int(input())
L = [0 for i in range (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):
def ryuka():
    N = int(input())
    
    if N==0:
        return 2
    elif N==1:
        return 1

    L = 1
    L_2 = 0
    L_1 = 2
    for i in range(2,N+1):
        L_2 = L_1
        L_1 = L
        L = L_1 + L_2
    return L
        
print(ryuka())

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

print(L[N])

Solution (Python):
l_dict = {}


def lucas(num):
    if num == 0:
        return 2
    elif num == 1:
        return 1
    elif num in l_dict:
        return l_dict[num]
    else:
        lu = lucas(num-1) + lucas(num-2)
        l_dict[num] = lu
        return lu


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

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

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

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

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

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

Solution (Python):
def lucas(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    prev_prev = 2
    prev = 1
    for i in range(2, n+1):
        current = prev + prev_prev
        prev_prev = prev
        prev = current
    return current
        

if __name__ == '__main__':
    print(lucas(int(input())))

Solution (Python):
import math
import sys

def getinputdata():

    
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

n = int(arr_data[0][0])

arr=[2,1]

for i in range(2,n+1):


    
    arr.append(arr[i-2]+arr[i-2+1])
    
print(arr[n])

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

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

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

Solution (Python):


li = [2,1]
num = int(raw_input())
for i in range (num-1):
    li.append(li[-1]+li[-2])
print li[-1]

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

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()

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

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

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

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

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

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

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

Solution (Python):





if __name__ == '__main__':
    number = int(input())

    lucas_numbers = [2, 1]

    if number >= 2:
        for i in range(2, number + 1):
            new_value = lucas_numbers[i - 1] + lucas_numbers[i - 2]
            lucas_numbers.append(new_value)

        print(lucas_numbers[number])
    else:
        print(lucas_numbers[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 = {0:2,1:1}
def lucasnumber(i):
    if i in Lucas:
        return Lucas[i]
    else:
        Lucas[i] = lucasnumber(i-1) + lucasnumber(i-2)
        return Lucas[i]
print(lucasnumber(N))

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

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

Solution (Python):
def main():
    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])
    

if __name__ == "__main__":
    main()

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

Solution (Python):
import sys
import math
import collections
import itertools
import array
import inspect


sys.setrecursionlimit(10000)


def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))


def to_bin(x):
    return bin(x)[2:]


def dim2input(N):
    li = []
    for _ in range(N):
        li.append(list(map(int, input())))
    return li



dp = None

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

    L = [2, 1]

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

    print(L[N])

main()

Solution (Python):


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

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

print(b)

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

Solution (Python):
n = int(input())
kai= 2
alm=1
alm2=1
for i in range(n-1):
    alm +=  kai
    kai=alm2
    alm2=alm
print(alm)

Solution (Python):
import functools

n=int(input())

@functools.lru_cache()
def luca(n):
    if n>=2:
        return luca(n-1) + luca(n-2)
    elif n==1:
        return 1
    else:
        return 2


print(luca(n))

Solution (Python):
N = int(input())
L = 2
l = 1

for i in range(N-1):
    if i%2==0:
        L = L+l
    else:
        l = l+L
if N%2==0:
    print(L)
else:
    print(l)

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

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

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

print(L[n])

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

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

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

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

b=2
c=1

for i in range (a):
    if i%2==0:
        b=b+c
    else:
        c=c+b

if b >c:
    print(c)
else:
    print(b)

Solution (Python):
import time
import sys

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

def main():
    N = input()
    if(int(N) == 0):
        print(2)
        sys.exit()
    elif(int(N) == 1):
        print(1)
        sys.exit()
    else:
        print(fib(int(N)+1))

if __name__ == '__main__':
    main()

Solution (Python):
def Lucas(n):
    L = [0]*(n+1)
    if n==0:
        return 2
    elif n == 1:
        return 1
    else:
        L[0]=2
        L[1]=1
        i=2
        while i < (n+1):
            L[i] = L[i-1]+L[i-2]
            i += 1
    return L[n]
N=int(input())
print(Lucas(N))

Solution (Python):
N = int(input())
a = []
a.append(2) 
a.append(1) 

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

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

Solution (Python):

N = int(input())

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

print(L[N])

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

Solution (Python):
def Lucas():
    a = 2
    b = 1
    while True:
        yield b
        (a, b) =  (b, a + b)

N = int(input())

for i, x in enumerate(Lucas()):
    if i == N-1:
        print(x)
        break

Solution (Python):
n = int(input())
c = 3
v = []

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

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

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

Solution (Python):

a = 2
b = 1

step = int(input()) - 1

for _ in range(step):
    a, b = b, a + b

print(b)

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

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 = [0]*87
ryuka[0] = 2
ryuka[1] = 1

def culc_ryuka(N, ryuka):
    for i in range(2, N+1):
        ryuka[i] = ryuka[i-1]+ryuka[i-2]
        
    return ryuka

ryuka = culc_ryuka(N, ryuka)
print(ryuka[N])

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

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

def luca(n, a, b):
    if n == 0:
        return a
    if n == 1:
        return b
    
    return luca(n - 1, b, a + b)

print(luca(N, 2, 1))

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

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

print L[n]

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

Solution (Python):
array=[-1]*87
array[0]=2
array[1]=1
def ryuka(n):
    if array[n] != -1: return array[n]
    if(n==0 or n==1): return array[n]
    else:
        array[n]=ryuka(n-1)+ryuka(n-2)
        return array[n]

N = int(input())

print(ryuka(N))

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

for i in range(2, 99):
    LC[i] = LC[i-1] + LC[i-2]
    
N = int(input())

print(LC[N])

Solution (Python):
def Lucas(n):
  if n==0: return 2
  if n==1: return 1
  a=2
  b=1
  for i in range(2,n+1):
    a,b=b,a+b
  return b
N=int(input())
print(Lucas(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())

Lx = 2
Ly = 1

if N == 1:
    print(Ly)
else:
    for i in range(N - 1):
        tmp = Lx + Ly
        Lx = Ly
        Ly = tmp
    print(Ly)

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

b=2

e=2
r=1

for i in range(n):
    if b%2==0:
        e=e+r
        b=b+1
    elif b%2==1:
        r=r+e
        b=b+1
    f=e
    g=r

if f>g:
    print(g)
elif f<g:
    print(f)

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

def ryuka(N):
	L = [0]*(N+2)
	L[0]=2
	L[1]=1
	for i in range(N):
		L[i+2]=L[i+1]+L[i]
	return L[N]

ans = ryuka(N)
print(ans)

Solution (Python):


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

Solution (Python):
N = int(input())
luca_tbl = {}
def lucas(X):
    if X in luca_tbl:
        return luca_tbl[X]
    else:
        if X == 0:
            luca_tbl[0] = 2
            return 2
        elif X == 1:
            luca_tbl[1] =1
            return 1
        else:
            luca_tbl[X] = lucas(X-1)+lucas(X-2)
            return lucas(X-1)+lucas(X-2)
            
print(lucas(N))

Solution (Python):
N = int(input())
L = [2,1]
def Lucas(n):
    if n < len(L):
        return L[n]
    L.append(Lucas(n-1) + Lucas(n-2))
    return L[n]
print(Lucas(N))

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

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

Solution (Python):


L = [2, 1]

N = int(raw_input())

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

print L[N]

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

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

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

Solution (Python):
n = int(input())
n += 1
ln0 = 2
ln1 = 1
if n == 0:
    print(ln0)
elif n==1:
    print(ln1)
else:
    for i in range(n-2):
        now = ln1
        ln1 = ln1+ln0
        ln0 = now
    print(ln1)