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

A = 1
B = 2
C = 0
for i in range(n-1):
    C = A + B
    B = A
    A = C
if n == 0:
    print(2)
elif n == 1:
    print(1)
else:
    print(C)

Solution (Python):
N = int(input())
l_im2, l_im1, l_i = 2, 1, 1
for i in range(2, N + 1):
	l_i = l_im1 + l_im2
	l_im1, l_im2 = l_i, l_im1
print(l_i)

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

lf = 2
ls = 1
for _ in range(n-1):
    lf, ls = ls, lf + ls

print(ls)

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

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

  print(c)

Solution (Python):
N = int(raw_input())
lis = [None]*87
lis[0] = 2
lis[1] = 1
for i in xrange(85):
	lis[i+2] = lis[i+1] + lis[i]
print lis[N]

Solution (Python):
l = [2, 1]
def a(N): 
    global l
    if(N == 0):
        return 2
    if(N == 1):
        return 1
    if(len(l) > N):
        return l[N]
    ans = a(N - 1) + a(N - 2)
    l.append(ans)
    return ans
    
N = input()
print a(N)

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

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

if __name__=='__main__':
    main()

Solution (Python):

N = int(raw_input())

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

Solution (Python):


def Lucas(n):
    a, b, c = 2, 1, 3
    while n != 0:
        a, b, c = b, c, b+c
        n -=1
    
    print a

Lucas(int(raw_input()))

Solution (Python):


num = int(input())

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

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

print(L[num])

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())
i = 1
prev = 2
x = [2, 1]

while i < n:
    if i == n:
        break
    x.append(x[i-1] + x[i])
    i = i + 1

print(x[n])

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

Solution (Python):
def calc(n, a, b):
    if n == 1:
        return b
    ls = [0 for i in range(n + 1)]
    ls[0], ls[1] = a, b
    for i in range(2, n + 1):
        ls[i] = ls[i - 1] + ls[i - 2]
    return ls[-1]

n = int(input())
print(calc(n, 2, 1))

Solution (Python):
def calc(n, a, b):
    if n == 1:
        return b
    ls = [0 for i in range(n + 1)]
    ls[0] = 2
    ls[1] = 1
    for i in range(2, n + 1):
        ls[i] = ls[i - 1] + ls[i - 2]
    return ls[-1]

n = int(input())
print(calc(n, 2, 1))

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

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

    print(L[-1])

if __name__ == "__main__":
    main()

Solution (Python):

N = int(input())

def lucas(M):
    a = 2
    b = 1
    
    if M > 1:
        for x in range(N-1):
            a,b = b,a+b
        return b
    elif M == 1:
        return 1
    elif M == 0:
        return 2 

print(lucas(N))

Solution (Python):



L = [2, 1]

n = int(input())

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

print(L[n])

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

Solution (Python):

import numpy as np

N = int(input())

ryuka = [2,1,3]

for i in range(N+1):
	if i>=3:
		R = (ryuka[i-1])+(ryuka[i-2])
		ryuka.append(R)
	else:
		pass

print(ryuka[N])

Solution (Python):


N=int(input())
A=2
B=1
sum=1

for i in range(0, N-1):
    
    sum=A+B
    A=B
    B=sum

print(sum)

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

Solution (Python):

"""
https://beta.atcoder.jp/contests/abc079/tasks/abc079_b

"""
import sys
from sys import stdin
from functools import lru_cache
input = stdin.readline


@lru_cache()
def solve(N):
    if N == 0:
        return 2
    elif N == 1:
        return 1
    return solve(N - 1) + solve(N - 2)



def main(args):
    N = int(input())
    ans = solve(N)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

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

    print(L1)

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

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

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

print(l[n])

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

Solution (Python):

table = [0]*90
def L(i):
    if i == 0:
        table[i] = 2
    elif i == 1:
        table[i] = 1
    else:
        table[i] = table[i- 1] + table[i-2]

s = int(input())
for i in range(s + 1):
    L(i)
print(table[s])

Solution (Python):


N = int(input())
Lin2 = 2
Lin1 = 1

if N > 1:
    for i in range(N-1):
        Li = Lin1 + Lin2
        Lin2 = Lin1
        Lin1 = Li
else:
    Li = 1

        
print(Li)

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



def f(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    elif n == 2:
        return 3
    return 2 * f(n - 2) + f(n - 3)


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

    return L[-1]


print(g(N))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    m = {0: 2, 1: 1}
    def f(i):
        if i in m:
            return m[i]
        a = f(i-1)
        b = f(i-2)
        m[i] = a+b
        return m[i]


    return f(n)



print(main())

Solution (Python):

import fileinput

for row in fileinput.input():
    N = int(row.strip())
    L = 2
    R = 1
    for i in range(N-1):
        L_N = L + R
        L = R
        R = L_N
    if N>1:
        print L_N
    elif N==1:
        print R
    elif N==0:
        print L

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

a = 2
luca = 1

for i in range(1,N):
  c = luca
  luca = a+luca
  a = c
  
print(luca)

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

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

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

Solution (Python):

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

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

ryuka = [2,1]

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

print ryuka[n]

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


def solve():
    N = int(input())
    print(fib(N + 1))
    

solve()

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

Solution (Python):
def main():
	n = int(input())
	dp = [2,1]
	for i in range(2,100):
		dp.append(dp[i-2]+dp[i-1])
	print(dp[n])
if __name__ == '__main__':
    main()

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

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

def calc(p, s):
    return p + s

def main():
    l0 = 2
    l1 = 1
    if N == 1:
        print(l1)
    else:
        p = l0
        s = l1
        for i in range(N - 1):
            temp = calc(p, s)
            p = s
            s = temp
        print(s)

if __name__ == '__main__':
    main()

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

Solution (Python):

Lucas=[2,1]
while Lucas[-1] < 1000000000000000000:
    Lucas.append(Lucas[-1]+Lucas[-2])
print(Lucas[int(input())])

Solution (Python):
def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    if table[n-1] != 0:
        t1 = table[n-1]
    else:
        table[n-1] = lucas(n-1)
        t1 = table[n-1]
    if table[n-2] != 0:
        t2 = table[n-2]
    else:
        table[n-2] = lucas(n-2)
        t2 = table[n-2]
    return t1 + t2


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

if __name__ == '__main__':
    table = [0 for _ in range(86)]
    main()

Solution (Python):

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

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

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

Solution (Python):
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)


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


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


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

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

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

Solution (Python):
s = int(input())
n = {0:2, 1:1}
if s > 1:
  for i in range(2, s+1):
  	n[i] = n[i-1] + n[i-2]
print(n[s])

Solution (Python):

def lucas(x):
  list = []
  list.append(2)
  list.append(1)
  i = 2
  while i <= x:
    list.append(list[i-1]+list[i-2])
    i += 1
  return list
      
 
if __name__ == '__main__':
  inputstr = input()
  num = int(inputstr)
  list = lucas(num)
  ans = list[num]
  print(ans,flush=True)

Solution (Python):

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

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

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

print(Luca(N))

Solution (Python):
n = 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())
a=2
b=1
if n==1:
    print(1)
    exit()
else:
    for i in range(2,n+1):
        c=b+a
        a=b
        b=c

    print(c)

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

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

Solution (Python):
N = int(input())
memo = [0] * 87
def luca(n):

  if n == 0:
    return 2
  elif n == 1:
    return 1

  if not memo[n]:
    memo[n] = luca(n - 2) + luca(n - 1)
  return memo[n]

print(luca(N))

Solution (Python):
lucas_list = [-1 for i in range(87)]
lucas_list[0] = 2
lucas_list[1] = 1

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

def solve():
    N = int(input())
    print(lucas(N))

solve()

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

Solution (Python):


n=int(raw_input())
l=[0 for i in xrange(87)]
l[0]=2
l[1]=1
for i in xrange(2,n+1):
 l[i]=l[i-1]+l[i-2]
print l[n]

Solution (Python):

N = int(input())

L = [2, 1]

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

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

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

Solution (Python):


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

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

print L[N]

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

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

print(L[-1])

Solution (Python):
memo = [2, 1] + 85 * [0]
def luca(n):
	if memo[n] != 0 :
		return memo[n]
	else :
		memo[n] = luca(n - 1) + luca(n - 2)
		return memo[n]

n = int(input())
print(luca(n))

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

Solution (Python):
import sys

N = int(input())

L0=2
L1=1

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

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):
l = [2, 1]
for x in xrange(100):
    l.append(l[-2] + l[-1])
print l[input()]

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

L0 = 2
L1 = 1
L = L1 + L0

N = int(input())

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

if N == 1:
  print(L1)
elif N == 2:
  print(L1 + L0)
else:
  print(L)

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

Solution (Python):



N = int(raw_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):
a=input()
x=2
y=1
z=1
for i in range(a-1):
    z=x+y
    x=y
    y=z

z=str(z)
print z

Solution (Python):


N = int(input())

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

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

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

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

Solution (Python):

N = str, input()
num = int(N[1])

L0 = 2
L1 = 1
x = 1
for i in range(1, num):
    x = L1 + L0
    L0 = L1
    L1 = x

print(x)

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

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

Solution (Python):
def main():
    n = 90
    a = [0 for i in range(n)]
    a[0],a[1] = 2,1

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

    print(a[int(input())])

if __name__ == '__main__':
    main()

Solution (Python):


from sys import stdin

def solve(N):
  l = [2, 1]
  if N <= 0: return l[N]
  for i in range(2, N + 1):
    lx = l[0] + l[1]
    l[0] = l[1]
    l[1] = lx
  return l[1]

N = int(stdin.readline())
print(solve(N))

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


def solve():
    N = int(input())
    print(fib(N + 1))
    

solve()

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

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

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

print(ans)

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

Solution (Python):

n = int(raw_input())

def lucas(n):
	if n == 0:
		return 2
	elif n == 1:
		return 1

	pre_num = 2
	cur_num = 1
	for i in range(1, n):
		rtn_num = cur_num + pre_num
		pre_num = cur_num
		cur_num = rtn_num
	return rtn_num

print(lucas(n))

Solution (Python):
import sys

DBG_FLAG = 0

def p_dbg(str):
    if(DBG_FLAG == 1):
        sys.stdout.flush()
        print str












def lucas_num(num):
    array = []
    array.append(2) 
    array.append(1) 
    p_dbg('array' + str(array))
    count = 2
    while count <= num:
        l1 = array[count -1]
        l2 = array[count -2]
        array.append(l1 + l2)
        count = count + 1

    p_dbg('array' + str(array))
    return array[num]


num = int(raw_input())
p_dbg('num : ' + str(num))

print lucas_num(num)

Solution (Python):

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


N = int(raw_input())

a, b, c = 2, 1, 3

if N == 0:
    print a
elif N == 1:
    print b
elif N == 2:
    print c

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

Solution (Python):
a = int(input())
R0 = 3
R1 = 2
R2 = 1
R = int((a-1)/3)
if a == 1:
  print("1")
elif a == 2:
  print("3")
elif a == 3:
  print("4")
else:
  for i in range(R):
    R1 = R2+R0
    R2 = R0+R1
    R0 = R1+R2
  if a%3 == 0:
    R1 = R2+R0
    print(R1)
  elif a%3 == 1:
    print(R2)
  else:
    print(R0)

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

ryuka[0] = 2
ryuka[1] = 1

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

print(ryuka[N])

Solution (Python):

from functools import lru_cache

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

num = int(input())

print(function(num))

Solution (Python):


def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)

if n == 0:
    print(2)
elif n == 1:
    print(1)
else:
    lucas0 = 2
    lucas1 = 1
    lucas = lucas0 + lucas1
    prev_lucas = lucas1
    for i in range(2, n):
        next_lucas = lucas + prev_lucas
        prev_lucas = lucas
        lucas = next_lucas
    print(lucas)

Solution (Python):
import sys,collections
sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()

lu = [0]*87
lu[0] = 2
lu[1] = 1

def luka(n):
    return lu[n-1] + lu[n-2]

for i in range(2,87):
    lu[i] = luka(i)

print(lu[n])

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

Solution (Python):
import sys

def ryuka(i):
    if i == 0:
        return 2
    elif i == 1:
        return 1
    else:
        return ryuka(i-1) + ryuka(i-2)

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


n = int(input())
print (eryuka(n))

Solution (Python):

from functools import lru_cache


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


if __name__ == "__main__":
    n = int(input())
    dict = {0:2, 1:1}
    print(test2(n))

Solution (Python):
def luca(a, b, num, c=0):
    if c == num:
        print(a)
    else:
        c += 1
        luca(b, a+b, num, c)

n = int(input())
luca(2, 1, n)

Solution (Python):

n = int(input())

ans = 4
pre = 1
prepre = 2

if n == 1:
    ans = 1
elif n == 2:
    ans = 3
elif n == 3:
    ans = 4
else:
    for n in range(n - 3):
        ans += pre + prepre
        a = prepre
        prepre = pre
        pre = pre + a

print(ans)

Solution (Python):


L_hi = 1
L_lo = 2

for _ in range(int(input())-1):
    L_hi, L_lo = L_hi+L_lo, L_hi
print(L_hi)

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

print(l[N])

Solution (Python):
def main():
    N=int(input())
    if(N==1):
        print(1)
        return
    K=0
    L=2
    M=1
    for i in range(N-1):
        K=L+M
        L=M
        M=K
    print(K)

if(__name__=="__main__"):
    main()

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

ans_list = [2,1]

for n in range(input_num - 1):
    num = ans_list[-1] + ans_list[-2]
    ans_list.append(num)


print(ans_list[-1])

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


def fibn(a, b, k, n):
    if k < n:
        return fibn(b, a+b, k+1, n)
    else:
        return a+b
if N == 1:
    print(1)
else:
    print(fibn(2,1,2,N))

Solution (Python):
N = int(input())
if N == 1:
    print(1)
else:
    l = 2
    r = 1
    for i in range(N - 1):
        L = l + r
        l = r
        r = L
    print(L)

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

if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    sub = [2, 1]
    for i in range(N - 3):
        if i % 2:
            sub[0] = sum(sub)
        else:
            sub[1] = sum(sub)
    if N % 2:
        print(sub[0] + 2 * sub[1])
    else:
        print(sub[1] + 2 * sub[0])

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

print(a[N])

Solution (Python):
import numpy as np

def L_n(num):
    if num==0:
        return 2
    elif num==1:
        return 1
    else:
        M = np.array([[1,1],[1,0]])
        V = np.array([[1],[2]])
        for i in range(num-1):
            V = np.dot(M,V)
        return V[0][0]

if __name__ == '__main__':
    IN = int(input())
    print(L_n(IN))

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

A = 1
B = 2
C = 0
for i in range(n-1):
    C = A + B
    B = A
    A = C
if n == 0:
    print(2)
elif n == 1:
    print(1)
else:
    print(C)

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

N = int(input())
lucas_number(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):
import functools


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


print(f(int(input())))

Solution (Python):
if __name__=="__main__":
    N = int(input())+1
    i0 = 2
    i1 = 1
    if N==1:
        print(2)
    elif N==2:
        print(1)
    else:
        temp_x=i0
        temp_y=i1
        temp = 0
        i = 3
        while not i>N :
            temp = temp_x+temp_y
            temp_x = temp_y
            temp_y = temp
            i+=1
        print(temp)

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

zero = 2
one = 1

res = 0
for i in range(num-1):
    res = zero + one
    zero = one
    one = res
if num < 2:
    print(1 if num ==1 else 2)
else:
    print(res)

Solution (Python):
import numpy as np

def luka(n):
    a,b=1,2
    if n==1:
        pass
    elif n>=1:
        for _ in range(n-1):
            a,b=a+b,a
    
    print(a)
    

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

    luka(N)

if __name__=="__main__":
    main()

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

Solution (Python):
num = list(map(int, input().split()))
a = [2,1]
for i in range(86):
 temp = a[i] + a[i+1]
 a.append(temp)

ans = int(num[0])
print(a[ans])

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

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

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

print(L[N])

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

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

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

print(a[n])

Solution (Python):

import numpy as np
n = int(input())
a1 = 2
a2 = 1
flag = 1
for i in range(0, n):
    if flag == 1:
        a1 = a1 + a2
        flag = 0
    else:
        a2 = a1 + a2
        flag = 1

if flag == 1:
    print(a1)
else:
    print(a2)

Solution (Python):
N = int(raw_input())
a = 2 
b = 1 
na = None
nb = None
for i in range(N-1):
    na = b 
    nb = a + b 
    a = na
    b = nb
print(b)

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

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

Solution (Python):
def L(n):
    a = 2
    b = 1
    res = 1
    for i in range(n - 1):
        res = 0
        res += a + b
        a = b
        b = res
    return res
print(L(int(input())))

Solution (Python):



"""abc079_b"""

import sys
import pprint
import re

import itertools
pp = pprint.PrettyPrinter(indent=2)

def main():
    """Main function."""
    n = int(input())

    l = [2,1]

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


if __name__ == '__main__':
    sys.exit(main())

Solution (Python):
N = int(input())
if N==1:
  import sys
  print(1)
  sys.exit()
  
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())

L0 = 2
L1 = 1
L2 = 3
if N == 0:
    print(L0)
elif N==1:
    print(L1)
else:
    ans = {}
    ans[0] = L0
    ans[1] = L1
    for i in range(2,N+1):
        ans[i] = ans[i-1]+ans[i-2]
    print(ans[N])

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

L = [2,1]
if a == 0:
    print(2)
elif a == 1:
    print(1)
else:
    for x in range(2,a+1):
        L.append(L[x-1]+L[x-2])
    print(L[a])

Solution (Python):
N=input()

L0=2
L1=1
L=0

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

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

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

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

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

print(r[-1])

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

L = [2,1]

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

print(L[-1])

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

Solution (Python):
N = int(input())
def solve(N):
    if N == 1: return 1
    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]
    return l[N]
print(solve(N))

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

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

def luka(n):
    luka_memo = [-1 for i in range(87)]
    luka_memo[0] = 2
    luka_memo[1] = 1
    for i in range(2,n+1):
        luka_memo[i] = luka_memo[i-1] + luka_memo[i-2]
    return luka_memo[n]

print(luka(N))

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

a0 = 2
a1 = 1

if n == 0:
  print(a0)
elif n == 1:
  print(a1)
else:
  for _ in range(n-1):
    tmp = a1
    a1 += a0
    a0 = tmp
  print(a1)

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

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

    print(num[N])

main()

Solution (Python):


if __name__ == '__main__':
    N = input()
    n0 = 2
    n1 = 1
    if N == 1:
        print(1)
    else:    
        now = 1
        while now != N:
            n = n0 + n1
            n0 = n1
            n1 = n
            now += 1
        print(n)

Solution (Python):


import sys

n = int(input())

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

print(max(ryuka))

Solution (Python):
a = [2,1,3]
count  = 3
while(count < 87):
    a.append(a[count-1]+a[count-2])
    count += 1
N=input()
print(a[int(N)])

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

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

print(L[n])

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

    print(f(N))


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

    return b

if __name__ == '__main__':
    main()

Solution (Python):
import sys

array = []
array.append(2)
array.append(1)
for i in range(85):
    array.append(array[i] + array[i+1])

N = int(sys.stdin.readline().strip())

print(array[N])