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() )
memo = [-1] * (N+1)

def LucasNumber( i ):
    if i == 0: return 2
    if i == 1: return 1
    if memo[i] == -1:
        memo[i] = LucasNumber( i-1 ) + LucasNumber( i-2 )
    return memo[i]

print( LucasNumber(N) )

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

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

A = [0, 2, 1]

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

print(A[n+1])

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

Solution (Python):

num=int(input())

def lucas(n):
    lus = [2, 1]
    for idx in range(n+1):
        if idx > 1:
            lus.append(lus[-2]+lus[-1])
    return lus[-1]
            
print(lucas(num))

Solution (Python):
N = int(input())
cache = {}
def culc(n):
    if n == 0:
        c = 2
    elif n == 1:
        c = 1
    else:
        if n-1 not in cache:
            cache[n-1] = culc(n-1)
        a = cache[n-1]
        if n-2 not in cache:
            cache[n-2] = culc(n-2)
        b = cache[n-2]
        c = a + b
    return c

print(culc(N))

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

Solution (Python):
n = int(input())
memo = [0]*87
def f(i):
    if memo[i]:
        return memo[i]
    if i==0:
        return 2
    elif i==1:
        return 1
    else:
        memo[i] = f(i-1)+f(i-2)
        return memo[i]
print(f(n))

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

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

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

Solution (Python):
n = int(input())
if n == 1:
    print(1)
    exit()

i = 2
L = [0]*(n+1)
L[0] = 2
L[1] = 1
while i != n:
    L[i] = L[i-1]+L[i-2]
    i+=1

print(L[n-1]+L[n-2])

Solution (Python):
n=int(input())
for i in range(n+1):
    if i==0:
        l=2
    elif i==1:
        l=1
        s1=1
        s2=2
    else:
        l=s1+s2
        s2=s1
        s1=l
print(l)

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

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

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

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

L0 = 2
L1 = L = 1

for i in range(N-1):
    L = L0 + L1
    L0 = L1
    L1 = L

print(L)

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

print(l[2])

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

print(n)

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

print(L[n])

Solution (Python):
""" AtCoder """

N = int(input())

l = [2, 1]

for _ in range(85):
    l.append(l[-1] + l[-2])

print(l[N])

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

cur = 1
pre = 2

for i in range(N - 1):
  cur, pre = cur + pre, cur

print(cur)

Solution (Python):
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools

def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

def swap(s,pos):
    s[pos]-=1
    s[pos+1]+=1
    print(s)
    if pos == n-2: return s
    if s[pos+2] == 0: swap(s,pos+1)
    return s


n = ip()                              














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

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

print(list[N])

Solution (Python):
def getLucas(N):
    if N == 0:
        return 2
    if N == 1:
        return 1

    l = [2, 1]

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

    return l[N]


N = int(input())
print(getLucas(N))

Solution (Python):
def luca(n, a=1, b=2):
  if n <= 1:
    return a
  return luca(n-1, a+b, a)

a = int(input())
print(luca(a))

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

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

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

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

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

print(Ryuka[N])

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

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

Solution (Python):
N=int(input()) 
tmpb=2 
tmpa=1 
num=0 
for i in range(N-1): 
    num=tmpb+tmpa 
    tmpb=tmpa 
    tmpa=num 
if N==1:
    num=1
print(num)

Solution (Python):
N = int(input())
L = [0]*87
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 = 87
m = int(input())
dp =[0]*(n+1)
dp[0]=2
dp[1]=1

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

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

array = [2, 1]

for i in range(int_n - 1):
    array.append(array[i] + array[i+1])

print(array[-1])

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

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

print(a[n])

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

for i in range(n-1):
    if n==1 or n==0:
        break
    else:
        a.append(a[i]+a[i+1])

print(a[n])

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

for i in range(n):
    if n==1 or n==0:
        break
    else:
        a.append(a[i]+a[i+1])

print(a[n])

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

for i in range(n+1):
    if n==1 or n==0:
        break
    else:
        a.append(a[i]+a[i+1])

print(a[n])

Solution (Python):
def lucas(n):
  if n==1:return 1
  l=[""]*(n+1)
  l[0]=2
  l[1]=1
  for i in range(2,n+1):
    l[i]=l[i-2]+l[i-1]
  return l[n]

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

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

Solution (Python):
def memoize(f):
    cache={}
    def helper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return helper

@memoize
def ans(N):
    if N==0:
        return 2
    elif N==1:
        return 1
    else:
        return ans(N-1)+ans(N-2)

N=int(input())
print(ans(N))

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

for _ in range(n-1):
    Table.append(sum(Table))
    Table.pop(0)
print(Table[1])

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

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

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

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

print(b[a])

Solution (Python):
d = {}


def func(n):
    if n == 0:
        return 2
    if n == 1:
        return 1

    if d.get(n - 1):
        r1 = d.get(n - 1)
    else:
        r1 = func(n - 1)
        d[n - 1] = r1

    if d.get(n - 2):
        r2 = d.get(n - 2)
    else:
        r2 = func(n - 2)
        d[n - 2] = r2
    return r1 + r2


def main():
    n = int(input())
    print(func(n))


if __name__ == '__main__':
    main()

Solution (Python):

def getInt(): return int(input())
def zeros(n): return [0]*n

N = getInt()
l = zeros(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())
a = 2
b = 1
if n == 1:
    print(b)
else:
    for i in range(n-1):
        c = a+b
        a = b
        b = c
    print(c)

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):
L_a,L_b = 1,2
N = int(input())
for i in range(N-1):
    L_a,L_b = L_a+L_b,L_a
print(L_a)

Solution (Python):
def inpl(): return list(map(int, input().split()))

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

print(luka[int(input())])

Solution (Python):
cache = {}

def f(x):
    if x == 0:
        return 2
    if x == 1:
        return 1
    
    if not x in cache:
        cache[x] = f(x - 1) + f(x - 2)
    return cache[x]


n = int(input())
print(f(n))

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

dp = [0]*87
dp[0],dp[1] = 2,1

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

print(dp[N])

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

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

L = [2,1]

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

print(L[n])

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

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

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

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

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

Solution (Python):
import numpy as np
a = int(input())
p =[0]*(a+1)
def cal(n):
    if p[n] !=0:return p[n]
    if n==0:res =  2
    elif n == 1:res = 1
    else: res =  cal(n-1)+cal(n-2)
    p[n] = int(res)
    return p[n]
print(int(cal(a)))

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):
memo=[0]*100
memo[0]=2
memo[1]=1
for i in range(2,100):
    memo[i]=memo[i-1]+memo[i-2]

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

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

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


def progression(L_, L__, i):
    if i <= N-1:
        L = L_ + L__
        i += 1
        return progression(L, L_, i)

    else:
        return L_


print(progression(L1, L0, 1))

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

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

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

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

"""
L = [0] * (N+1)
L[0], L[1] = 2, 1
def luka(n):
  for i in range(2,n+1):
    x = L[i-2] + L[i-1]
    L[i] = x
  return L[-1]
luka(N)
"""

Solution (Python):

N = int(input())
a = 2
b = 1

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

Solution (Python):

N = int(input())
L0 = 2
L1 = 1

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

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

a, b = 1, 2
i = 2
while i <= n:
  a, b = a + b, a
  i += 1

print(a)

Solution (Python):
def abc079_b():
    n = int(input())
    if n == 1:
        print(1)
    else:
        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])


abc079_b()

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):
buf=[-1 for i in range(90)]
def ryuka(N):
    global buf
    if buf[N]!=-1:
        return buf[N]
    else:
        if N==1:
            return 1
        elif N==0:
            return 2
        else:
            buf[N]=ryuka(N-1)+ryuka(N-2)
            return ryuka(N-1)+ryuka(N-2)

N=int(input())
print(ryuka(N))

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

def luca(n):
    a = [None] * (n+1)
    a[0] = 2
    a[1] = 1
    for i in range(2, n+1):
        a[i] = a[i-1] + a[i-2]
    return a[n]
 
if __name__ == "__main__":
    print(luca(n))

Solution (Python):



def main():
    """Function."""
    n = int(input())

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

    print(save[-1])


if __name__ == "__main__":
    main()

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

Solution (Python):
def main():
    n = int(input())
    ls = (2, -1)
    for _ in range(1, n + 1):
        ls = (ls[0] + ls[1], ls[0])
    print(ls[0])


if __name__ == '__main__':
    main()

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

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

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

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

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

Solution (Python):
import sys

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


def readQuestion():
    ws = sys.stdin.readline().strip().split()
    n = int(ws[0])
    return (n,)

def main():
    solve(*readQuestion())


main()

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

L1=2
L2=1

for i in range(1,N,2):
    L3=L1+L2
    L4=L2+L3
    L1=L3
    L2=L4
if(N==1):
    print("1")
elif(N%2==0):
    print(L3)
else:
    print(L4)

Solution (Python):
import sys

def solve(n):
    print(luca(n))
    

def luca(n):
    result = [0 for i in range(n+1)]
    result[0] = 2
    result[1] = 1
    for i in range(2,n+1):
        result[i] = result[i-1] + result[i-2]
    return result[n]

def luca_other(n):
    if n == 0:
        return 2
    (x, y) = (2, 1)
    for i in range(n-1):
        (x, y) = (y, x + y)
    return y

def readQuestion():
    ws = sys.stdin.readline().strip().split()
    n = int(ws[0])
    return (n,)

def main():
    solve(*readQuestion())


main()

Solution (Python):
N = int(input())
L0 = 2
L1 = 1
lst = [L1,L0]
for i in range(N-1):
    lst.insert(0,lst[0]+lst[1])

print(lst[0])

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

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

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

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

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

print(L[n])

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

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

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

Solution (Python):
def lucas(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    current = 0
    n_1 = 1
    n_2 = 2
    for i in range(n - 1):
        current = n_1 + n_2
        n_2 = n_1
        n_1 = current
    return current

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

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

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

a,b,c = 2,1,3

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

print(a)

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())
a=2
b=1

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

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

Solution (Python):
N = int(input())
def rk(n, memo):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    if memo[n] != 0:
        return memo[n]
    else:
        memo[n] = rk(n-1,memo) + rk(n-2,memo)
        return memo[n]
memo = [0 for i in range(87)]
print(rk(N, memo))

Solution (Python):
N = int(input())
def rk(n, memo):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    if memo[n] != 0:
        return memo[n]
    else:
        memo[n] = rk(n-1,memo) + rk(n-2,memo)
        return memo[n]
memo = [0 for i in range(87)]
print(rk(N, memo))

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

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

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

lucas_list = [2,1]
while len(lucas_list) <= N:
    i = len(lucas_list)
    lucas_list.append(lucas_list[i-2]+lucas_list[i-1])
print(lucas_list[N])

Solution (Python):
a = int(input())
ar = [2,1]
count = 2
if a == 1:
    print(1)
else:
    while count != a:
        count += 1
        ar.append(sum(ar))
        del ar[0]
    print(sum(ar))

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

print(L[N])

Solution (Python):
n = int(input())
l0 = 2
l1 = 1
s = 0
for i in range(n - 1):
  s = l0 + l1
  l0 = l1
  l1 = s

if n == 1:
  print(l1)
else:
  print(s)

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

Lucas_array = [2,1]
count = 0

while True:
    item = Lucas_array[count] + Lucas_array[count+1]
    if item < 10**18:
        Lucas_array.append(item)
        count += 1
    else:
        break

print(Lucas_array[n])

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

if n == 0:
	print(2)
else:
	print(Lucas(n-1))

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

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

for i in range(a):
  b.append(b[i]+b[i+1])
  
print(b[a])

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):
el_before = 2
el = 1
ans = 1
for i in range(2,int(input())+1):
    ans = el + el_before
    el_before = el
    el = ans
print(ans)

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

print(L[-1])

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

Solution (Python):
n = int(input())
x = 2
y = 1
z = 1
for i in range(1, n):
    z = x + y
    x = y
    y = z
print(z)

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

for n, l in enumerate(L):
    if n == 0:
        L[0] = 2
    elif n == 1:
        L[1] = 1
    else:
        L[n] = L[n-1] + L[n-2]

N = int(input())

print(L[N])

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

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

nums = {}
nums[0] = 2
nums[1] = 1
for i in range(2, 87):
    nums[i] = nums[i-1]+nums[i-2]
print(nums[N])

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

Solution (Python):
import functools

N = int(input())

@functools.lru_cache(maxsize = None)
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):
def luka(n):
  global lk
  if n==0:
    return 2
  if n==1:
    return 1
  if lk[n] != -1:
    return lk[n]
  lk[n] = luka(n-1)+luka(n-2)
  return lk[n]

lk = [-1]*100
n = int(input())
print(luka(n))

Solution (Python):


n = int(input())


m = []

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


def lucasnumber(n):
  if n == 0:
    return 2
  if n == 1:
    return 1
  if n == 2:
    return 3
  if n == 3:
    return 4
  return int(2*m[n-4]+m[n-3])

print(lucasnumber(n))

Solution (Python):
from sys import stdin


def main() -> None:
    n = int(next_str())
    lucas = [2, 1]

    for i in range(2, n + 1):
        lucas[i % 2] = sum(lucas)

    print(lucas[n % 2])


def next_str() -> str:
    result = ""
    while True:
        tmp = stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

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

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

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

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

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

print(ryuka(n))

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

print(x[-1])

Solution (Python):
def get_new_lucas(l_i_1, l_i_2):
    """
    get a new Lucas number L_i

    l_i_1: L_(i-1),
    l_i_2: L_(i-2)
    """
    return l_i_1 + l_i_2


def main():
    n = int(input())
    tmp_l_i_1 = 1
    tmp_l_i_2 = 2
    for i in range(n):
        if i == 0:
            new_lucas_num = 1
        if i >= 1:
            new_lucas_num = get_new_lucas(tmp_l_i_1, tmp_l_i_2)
            tmp_l_i_2 = tmp_l_i_1
            tmp_l_i_1 = new_lucas_num
        
    print(new_lucas_num)


if __name__ == '__main__':
    main()

Solution (Python):

from sys import stdin

n = int(stdin.readline().rstrip())
l_2 = 2
l_1 = 1
l_0 = 0

if n == 0:
    l_0 = l_2
elif n == 1:
    l_0 = l_1
else:
    for i in range(2,n+1):
        l_0 = l_2 + l_1
        l_2 = l_1
        l_1 = l_0
print(l_0)

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

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

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

L = [2,1]

for i in range(n+2):
	if i ==0 or i ==1:
		continue
	L.append(L[i-2]+L[i-1])
print(L[n])

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

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

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

print(a[n])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()

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

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

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

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

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

def Lucas(N):
  L0 = 2
  L1 = 1
  for _ in range(N-1):
    L = L0 + L1
    L0 = L1
    L1 = L
  
  return L

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

Solution (Python):
x = int(input())
def func(n):
    a,b = 2, 1
    while n > 1:
        a, b = b, a+b
        n -= 1
    return b
print(func(x))

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

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

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


print(l[len(l) - 1])

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

print(sumL[n])

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

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

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

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

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

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

Solution (Python):
a0 = 2
a1 = 1

for _ in range(int(input())-1):
	a0, a1 = a1, a0 + a1

print(a1)

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

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

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

print(Lucas[N])

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

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

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):
import numpy as np

N = int(input())

L = [2,1]

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


print(L[N])

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

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

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

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

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

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

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

print(L_list[N])

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

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

Solution (Python):
n = int(input())
l0 = 2
l1 = 1
if n == 0:
    print(l0)
    exit()
if n == 1:
    print(l1)
    exit()

l_prev = l0
l_next = l1

i = 2
while True:
    l_new = l_prev + l_next
    if n == i:
        print(l_new)
        break
    l_prev = l_next
    l_next = l_new
    i += 1

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

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

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

dp=[-1 for _ in range(N+1)]
def Lu(n):
    if n==0:
        rec=2
    elif n==1:
        rec=1
    elif dp[n]!=-1:
        return dp[n]
    else:
        rec=Lu(n-1)+Lu(n-2)
    dp[n]=rec
    return rec
print(Lu(N))