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-----
5

-----Sample Output-----
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.

Difficulty: introductory

Starter code:

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

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

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

n = int(input())

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

ans = num_list[n]
print(ans)

N = int(input())
l1 = 2
l2 = 1

for i in range(N-1):
  l1, l2 = l2, l1 + l2
print(l2)


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

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

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

N = int(input())

if N == 0:
  print(2)
elif N == 1:
  print(1)
else:
  
  n_2 = 2
  n_1 = 1
  
  for _ in range(N-1):
    n_0 = n_1 + n_2
    n_2 = n_1
    n_1 = n_0
    
  
  print(n_0)

import numpy as np
n = int(input())
l = np.zeros(87,dtype=int)
l[0] = 2
l[1] = 1
for i in range(2,87):
    l[i] = l[i-1] + l[i-2]
print(l[n])

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


N = int(input())

L = [2, 1]

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

print((L[-1]))


n = int(input())
l0 = 2
l1 = 1
sum_ = 1
for i in range(n-1):
    sum_ = l0 + l1
    l0 = l1
    l1 = sum_
print(sum_)


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

n = int(input())
calc_r = [0]*(n+1)
calc_r[0] = 2
calc_r[1] = 1

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

n=int(input())
s=[]
s.append(2)
s.append(1)
if n==1:
    print('1')
    return
else:
    for i in range(2,87):
        k = s[i-2]+s[i-1]
        s.append(k)
        if i==n:
            print((s[i]))
            return


n = int(input())

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

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

N = int(input())
L = [0] * 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])

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

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

print(l[n])

N = int(input())

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

L_2 = 2
L_1 = 1
for i in range(N-1):
    L = L_1+L_2
    L_2 = L_1
    L_1 = L
print(L)


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

def answer(n: int) -> int:
    if n == 1:
        return 1

    two_previous_l = 2
    previous_l = 1
    l = 3
    for _ in range(n - 2):
        two_previous_l = previous_l
        previous_l = l
        l = previous_l + two_previous_l

    return l


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


def __starting_point():
    main()

__starting_point()

n = int(input())
if n == 0:
  print(2)
  return
elif n == 1:
  print(1)
  return
  
q = [2,1]
for i in range(2,88):
  m = q[i-1]+q[i-2]
  q.append(m)
  
print(q[n])

n = int(input())
Luca = [0]*100
Luca[0] = 2
Luca[1] = 1

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

print(Luca[n])

N = int(input())

lucas_list = []

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

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

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

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

import sys
N = int(input())
if(N==1):
  print(1)
  return
ans = 0
L0 = 2
L1 = 1
for i in range(N-1):
  ans = L0 + L1
  L0 = L1
  L1 = ans
print(ans)

N = int(input())

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

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

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

N = int(input())
dp = [[]for i in range(87)] 
dp[0] = 2
dp[1] = 1

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

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

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

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

n = int(input())
l0 = 2
l1 = 1

if n == 1:
    print(l1)
else:
    for i in range(n-1):
        ln = l0 + l1
        l0 = l1
        l1 = ln
    print(ln)

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

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


import sys
import copy
import math
import itertools
import numpy as np
N = int(input())
L=[2,1]
for i in range(N-1):
    L.append(L[i]+L[i+1])

print(L[N])

from collections import defaultdict


def mapt(fn, *args):
    return tuple(map(fn, *args))


def Input():
    return mapt(int, input().split(" "))


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


main()

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

N = int(input())

L = [2, 1]

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

print(L[-1])

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

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

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


n=int(input())
a=2
b=1
i=0
while i<n:
  d=a
  a=b
  b=d+b
  i=i+1
print(a)

N = int (input ())
L1,L2 = 2,1
L3 = 1
x = 1
for i in range (N-1):
  if x == 1:
    L1 = L1+L2
    L3 = L1
    x = 2
  else:
    L2 = L1+L2
    L3 = L2
    x = 1
print (L3)

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

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

n=int(input())

if n==1:
  print(1)
elif n==2:
  print(3)
else:
  ans=0
  num_1=2
  num_2=1
  for i in range(n-1):
    ans = num_1+num_2
    num_1,num_2 = num_2, ans
  print(ans)

# coding = SJIS

n = int(input())

luca = [2, 1]

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

else:
    print(1)

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

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

print((L[N]))


N = int(input())

if N == 1:
  print(1)
  return

L1 = 1
L0 = 2

for i in range(2,N+1):
  LC = L1 + L0
  L0 = L1
  L1 = LC
  
print(LC)

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()

    lucas = [0] * (N + 1)
    lucas[0] = 2
    lucas[1] = 1
    for i in range(N - 1):
        lucas[i+2] = lucas[i] + lucas[i+1]

    print((lucas[-1]))

def __starting_point():
    resolve()

__starting_point()

def __starting_point():

    n = int(input())

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

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

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

from functools import lru_cache
N = int(input())
@lru_cache(86)
def lucas(x):
  if x == 0:
    return 2
  if  x ==1:
    return 1
  else:
  
    return lucas(x-1) + lucas(x-2)
print(lucas(N))

n = int(input())
import sys
dp = [0]*(n+3)

dp[0]=2
dp[1]=1
if n<=1:
    print(dp[n])
    return

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

print(dp[n])

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

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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

n = int(input())

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

a = 2
b = 1
now = 3
count = 2
for i in range(2, n):
    a = b
    b = now
    now = a+b

print(now)


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

n = int(input())

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

print(lucas[-1])

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

N = int(input())

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


N=int(input())
s=2
t=1
for i in range(0,N):
    u=s+t
    s,t,u=t,u,s # sの変換をtにした。
    
print(s)


N = int(input())


def luca(n):
    a = 1
    b = 2
    for i in range(n):
        a, b = a+b, a
    return b


print(luca(N))


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

n = int(input())
data = [0]*87
data[0] = 2
data[1] = 1
if n >= 2:
    for i in range(2,n+1):
        data[i] =data[i-1] + data[i-2]
print(data[n])

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    numbers=[2,1]
    number = int(input())

    for i in range(2,number+1):
        numbers.append(numbers[i-1]+numbers[i-2])
    print(numbers[-1])
    
def __starting_point():
    main()
__starting_point()

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

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


n = int(input())

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

n = int(input())

a = [2,1]

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

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

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

#
# abc079 b
#
import sys
from io import StringIO
import unittest
from functools import lru_cache

sys.setrecursionlimit(10**9)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5"""
        output = """11"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """86"""
        output = """939587134549734843"""
        self.assertIO(input, output)


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

    print((L(N)))


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


def __starting_point():
    # unittest.main()
    resolve()

__starting_point()

from functools import lru_cache

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


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


N = int(input())
res = [2, 1]

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

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


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

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

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

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

print((l[n]))



N = int(input())
L = [2, 1]
if N == 1:
    print(1)
    return

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

N = int(input())

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

print(L[-1])

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


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

N = int(input())
ls = [0] * (N + 1)

ls[0], ls[1] = 2, 1

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

n = int(input())
if n == 1:
    print(1)
    return
x = 2
y = 1
ans = 0
for i in range(n-1):
    ans = x + y
    x = y
    y = ans
print(ans)

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

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[len(l) - 1])

lst = list()
lst.append(2)
lst.append(1)

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

print(lst[n])

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

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

def resolve():
    '''
    code here
    '''
    N = int(input())

    memo = [0 for _ in range(N+1)]
    memo[:2] = [2, 1]

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

    print((memo[N]))

def __starting_point():
    resolve()

__starting_point()

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

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

print(l[n])