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

L0 = 2
L1 = 1
L = L1
Lmin = L0

if N == 1:
  print(1)
  sys.exit()
for i in range(2, N+1):

  Li = L + Lmin
  Lmin = L
  L = Li

print(Li)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




N = ii()

A = [0] * (N+1)

A[0] = 2
A[1] = 1

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

print(A[N])

Solution (Python):




n = int(input())
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 calc(n, dp):
	if dp[n]:
		return dp[n]
	if n <= 1:
		return dp[n]
	dp[n] = calc(n-1, dp) + calc(n-2, dp)
	return dp[n]

def resolve():
	n = int(input())
	dp = [None] * 87
	dp[0], dp[1] = 2, 1
	print(calc(n, dp))
resolve()

Solution (Python):
n = int(input())
lucas = [2,1]
if n == 0:
  print(2)
elif n == 1:
  print(1)
t = 2
while t <= n:
  next_lucas = lucas[-1] + lucas[-2]
  lucas.append(next_lucas)
  if t == n:
    print(next_lucas)
  t += 1

Solution (Python):
def solve(n):

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

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

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

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

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

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

print(memo[-1])

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

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

print(dp[N])

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

Solution (Python):

import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**7)
rs = lambda: sys.stdin.readline().rstrip()
ri = lambda: int(rs())
rf = lambda: float(rs())
rs_ = lambda: [_ for _ in rs().split()]
ri_ = lambda: [int(_) for _ in rs().split()]
rf_ = lambda: [float(_) for _ in rs().split()]
INF = float('inf')
MOD = 10 ** 9 + 7
PI = math.pi

@lru_cache(maxsize=None)
def f(N):
    if N == 0: return 2
    if N == 1: return 1
    return f(N - 1) + f(N - 2)
print(f(ri()))

Solution (Python):
n=int(input())
ans=0
first=1
second=3
for i in range(n-2):
    ans=first+second
    first=second
    second=ans
print(ans if n>2 else "1" if n==1 else "3")

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())
l0 = 2
l1 = 1
if n==1:
  print(l1)
else:
  for i in range(n-1):
    sum = l0+l1
    l0 = l1
    l1 = sum
  print(sum)

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 lucas_number(n):
  l = [2, 1]
  l_i_1 = 1
  l_i_2 = 2
  if n == 1:
    return l[1]
  
  for i in range(n-1):
    tmpl = l[-1] + l[-2]
    l.append(tmpl)
    
  return l[-1]

n = int(input())
print(lucas_number(n))

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

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

print(ans[N])

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

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

print(l[n])

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

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

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

Solution (Python):

import sys
def input(): return sys.stdin.readline().strip()

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

Solution (Python):

import sys
def input(): return sys.stdin.readline().strip()

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

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

main()

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

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


if __name__ == '__main__':
    main()

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

sys.setrecursionlimit(1000000)




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

    if n == 1:
        print(1)
    else:
        _x2 = 2
        _x1 = 1
        _x = 0
        for i in range(n-1):
            _x = _x2 + _x1
            _x2 = _x1
            _x1 = _x

        print(_x)


main()

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7


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

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


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


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
arr = [2,1]
for i in range(2,87):
  arr.append(arr[i-2] + arr[i-1])
print(arr[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())
mem = [None]*100
def Lucas(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    if mem[n] is None:
        mem[n] = Lucas(n-2) + Lucas(n-1)
    return mem[n]
print(Lucas(n))

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

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

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

Luca = [2, 1]

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

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

print(lucas[-1])

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

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

print(p[n])

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

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

Lucas=[2,1]

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

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

Li_2 = 2
Li_1 = 1
Li = Li_2 + Li_1
for i in range(N-1):
    Li = Li_2 + Li_1
    Li_2 = Li_1
    Li_1 = Li

if N == 1:
  print(1)
else:
  print(Li)

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

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

Solution (Python):
n = int(input())
l0 = 2
l1 = 1
cnt = 2
l2 = l0 + l1
while cnt < n:
    l2, l1, l0 = l2 + l1, l2, l1
    cnt += 1
if n == 1:
    print(1)
else:
    print(l2)

Solution (Python):



N = int(input())


lucas = [0]*100


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]


print(lucas[N])

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]

def to_bin(x: int) -> str: return format(x, 'b') 
def to_oct(x: int) -> str: return format(x, 'o') 
def to_hex(x: int) -> str: return format(x, 'x') 
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]

from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left



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

def main():
    n = II()
    print(get_lucas(n))

if __name__ == '__main__':
    main()

Solution (Python):


n=int(input())

dict=[0 for _ in range(n+1)]
dict[0]=2
dict[1]=1

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

print(lucas(n))

Solution (Python):
import numpy as np
import sys

input = sys.stdin.readline

N = int(input())

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

l = [0]*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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

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

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

  
print(luca_list[N])

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

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

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

Solution (Python):
n = int(input())
L = [0 for _ in range(n+2)]
L[0]=2
L[1]=1
if n >= 2:
    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(2, n+1):
    l0, l1 = l1, l0 + l1
print(l1)

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

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

print(L[N])

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

a, b = 2, 1


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

print(b)

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

A=[0]*(N+1)
A[0]=2
A[1]=1
i=2
while i<=N:
    A[i]=A[i-1]+A[i-2]
    i+=1

print(A[N])

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

print(lyu[N])

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=[2,1]
ans=0

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

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

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

cnt=2
if N==1:
	print(1)
else:
	a=2
	b=1
	while cnt<=N:
		c=a+b
		
		a=b
		b=c
		cnt+=1
	print(c)

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

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


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

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


def func(n, memo):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    if n - 1 in memo:
        l = memo[n - 1]
    else:
        l = func(n - 1, memo)
        memo[n - 1] = l
    if n - 2 in memo:
        r = memo[n - 2]
    else:
        r = func(n - 2, memo)
        memo[n - 2] = r
    return l + r

memo = {}
ans = func(n, memo)
print(ans)

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]

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    l=[2,1]
    for i in range(N):
        l.append(l[i]+l[i+1])
    print(l[N])
    
    
if __name__ == '__main__':
    main()

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

Solution (Python):
from functools import lru_cache

n = int(input())

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

print(lucas(n))

Solution (Python):
n = int(input())
a1=1
a2=2
for i in range(n-1):
	a=a1+a2
	a2=a1
	a1=a
if n==1:
	a=1
	
print(a)

Solution (Python):
import sys
from collections import Counter
readline = sys.stdin.buffer.readline
MOD = 10**9+7

def main():
    N = int(readline())
    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])




if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
if n==1:
    print(1)
else:
    ans_1=1
    ans_2=2
    for _ in range(n-1):
        ans=ans_1+ans_2
        ans_2=ans_1
        ans_1=ans
        
        
    print(ans)

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

Solution (Python):

from functools import lru_cache


@lru_cache(maxsize=None)
def lucas(num):
    if num == 0:
        return 2
    elif num == 1:
        return 1
    else:
        return lucas(num - 1) + lucas(num - 2)


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


if __name__ == "__main__":
    main()

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

print(L2)

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

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

print(Lucas_num[num])

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

print(Lucas_num[num])

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

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

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


if __name__ == '__main__':
    main()

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

def main():
    N = int(readline())
    l0 = 2
    l1 = 1
    if N == 1:
        print(l1)
        return
    for i in range(2, N+1):
        li = l0 + l1
        l0 = l1
        l1 = li
    print(li)
    

if __name__ == '__main__':
    main()

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

Solution (Python):




from functools import lru_cache









N = int(input())

@lru_cache(maxsize=1000)
def lucas_number(n) -> int:
    if n<0:
        return -1
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        return lucas_number(n-1)+ lucas_number(n-2)

ans = lucas_number(N)

print(ans)

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

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

            

if '__main__' == __name__:
    resolve()

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

Solution (Python):
from functools import lru_cache

n = int(input())

@lru_cache(maxsize=10**5)
def f(x):
    if x == 0:
        return 2
    elif x == 1:
        return 1
    else:
        return f(x-1) + f(x-2)

print(f(n))

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

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

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

Solution (Python):
n = int(input())
x = 2
y = 1

if n == 1:
    ans = 1

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

print(ans)

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

Solution (Python):
def lucas(n):
    global nlist
    if n==0:
        return 2
    if n==1:
        return 1
    if nlist[n]!=0:
        return nlist[n]
    else:
        nlist[n]=lucas(n-1)+lucas(n-2)
        return lucas(n-1)+lucas(n-2)
    
nlist=[0 for a in range(100)]
print(lucas(int(input())))

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

from collections import Counter,deque

ryuka = deque([2,1])

for i in range(n):
    x = sum(ryuka)
    ryuka.popleft()
    ryuka.append(x)
ans = ryuka[0]
print(ans)

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

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

Solution (Python):




def calc_luca(n):
    if n==0:
        return luca[0]
    if n==1:
        return luca[1]
    if luca[n]!=0:
        return luca[n]
    luca[n] = calc_luca(n-1) + calc_luca(n-2)
    return luca[n]
N = int(input())
luca = [0]*(N+1)
luca[0] = 2
luca[1] = 1
print(calc_luca(N))

Solution (Python):
icase=0
if icase==0:
    n=int(input())
    lim2=2
    lim1=1
    if n==1:
        print(lim1)
    else:
        for i in range(n-1):
            li=lim1+lim2
            lim2=lim1
            lim1=li
        print(li)

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())
if n==0:
  print(2)
elif n==1:
  print(1)
else:
  pre1,pre2=1,2
  ans=0
  for i in range(n-1):
    ans=pre1+pre2
    pre1,pre2=ans,pre1
  print(ans)

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

if N == 1:
    b = 1
else:
    a, b = 2, 1
    for i in range(N-1):
        a, b = b, a+b

print(b)

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

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

print(a[n])

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

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

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

import io

nim = int(input())
mike = [2, 1]
for i in range(100):
    mike.append(mike[-1] + mike[-2])

print(mike[nim])

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

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

print(ans[n])

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

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

print(a[n])

Solution (Python):

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

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

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

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

L = [0] * 87
L[0] = 2
L[1] = 1
for i in range(2, len(L)):
    L[i] = L[i - 1] + L[i - 2]
print(L[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())
l = [2,1]
i = 2
while len(l)<N+1:
  l.append(l[i-1]+l[i-2])
  i+=1
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())

def defs(n):
    l0 = 2
    l1 = 1
    ans = 1
    if n == 1:
        return ans
    else:
        for i in range(2, n + 1):
            ans = l0 + l1
            l0 = l1
            l1 = ans
        return ans

print(defs(n))

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

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

    print(L[n])

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

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

Solution (Python):
def Lucas(L1,L2,n,end):
   return L1+L2 if(n==end) else Lucas(L1+L2,L1,n+1,end)
def myAnswer(N:int) -> int:
   if(N == 0):
      return 2
   elif(N == 1):
      return 1
   else:
      return Lucas(1,2,2,N)
def modelAnswer():
   tmp=1
def main():
   N = int(input())
   print(myAnswer(N))

if __name__ == '__main__':
   main()

Solution (Python):
def Lucas(L1,L2,n,end):
   if(n==end):
      print(L1+L2)
   else:
      Lucas(L1+L2,L1,n+1,end)
def myAnswer(N:int) -> None:
   if(N == 0):
      print(2)
   elif(N == 1):
      print(1)
   else:
      Lucas(1,2,2,N)
   

def modelAnswer():
   tmp=1
def main():
   N = int(input())
   myAnswer(N)

if __name__ == '__main__':
   main()

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

L0 = 2
L1 = 1
ans = 0

for i in range(2, N + 1):
    ans = L0 + L1
    L0 = L1
    L1 = ans
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):
import functools

N = int(input())

@functools.lru_cache(maxsize=None)
def find_lyuka(x):
    if x == 0:
        return 2
    elif x == 1:
        return 1
    else:
        return find_lyuka(x-1) + find_lyuka(x-2)

print(find_lyuka(N))

Solution (Python):
import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math

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

def findL(n):
    if n==0: return 2
    if n==1: return 1
    i2, i1 = 2, 1
    Luca = 0
    for i in range(2,n+1):
        Luca = i1 + i2
        i2 = i1
        i1 = Luca
    return Luca

print(findL(n))

Solution (Python):
n = int(input())
memo = [-1]*(n+1)

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

print(func(n))

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

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

Solution (Python):
n = int(input())
Lucas = [0]*87
Lucas[0] = 2
Lucas[1] = 1
for i in range(87):
    if i+2 > n:break
    Lucas[i+2] = Lucas[i+1]+Lucas[i]
print(Lucas[n])

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

L = [2,1]

for i in range(100):
  L.append(L[i]+L[i+1])

print(L[N])

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

Solution (Python):
def lucas_number(x):
    if x == 0:
        return 2
    if x == 1:
        return 1
    l = 2
    r = 1
    while x - 1 > 0:
        l, r = r, l + r
        x -= 1
    return r

n = int(input())
print(lucas_number(n))

Solution (Python):
n = int(input())
a1 = 1
a0 = 1

for i in range(0 ,n - 2):
    a1, a2 = a0, a1
    a0 = a1 + a2

if n == 0:
    print(2)
if n == 1:
    print(1)
if n == 2:
    print(3)
if n >= 3:
    print(a0 + a1 * 2)

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

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

print(L[N])