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

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

if __name__ == "__main__":
    main()

Solution (Python):
import math
from collections import deque
from collections import defaultdict


def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): 
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): 
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} 
def bitArr(n):
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): 
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	
	data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	
	ans = data[:]
	return ans

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



print(ryuka[readInt()])

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

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

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

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

Solution (Python):
def main():

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

main()

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

Solution (Python):
def lucas(n, memo={}):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = lucas(n - 1, memo) + lucas(n - 2, memo)
        return lucas(n - 1) + lucas(n - 2)


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

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

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

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

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

L = [-1] * 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):
n = int(input())
l = [0]*87
l[0] = 2
l[1] = 1

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

print(l[n])

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

dp = [-1] * 100
dp[0] = 2
dp[1] = 1

def f(x):
  if x == 0:
    return dp[0]
  
  if x == 1:
    return dp[1]

  if dp[x] == -1:
    dp[x] = f(x-1) + f(x-2)
    return dp[x]
  else:
    return dp[x]

print(f(n))

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

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

print(L[n])

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

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

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

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

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

print(ll[n])

Solution (Python):
n = int(input())
ans1 = 2
ans2 = 1
ans3 = 3
for i in range(1,n):
    ans3 = ans1 + ans2
    ans1 = ans2 
    ans2 = ans3
if n == 1:
    print(1)
else:
    print(ans3)

Solution (Python):
n = int(input())
ans1 = 2
ans2 = 1
ans3 = 3
for i in range(1,n):
    ans3 = ans1 + ans2
    ans1 = ans2 
    ans2 = ans3
if n == 1:
    print(1)
else:
    print(ans3)

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())
num=[2,1]
for i in range(n-1):
    num.append(num[-1]+num[-2])
print(num[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):
def calc_lucas(n):
  """
  Args:
    n (int)
  Returns:
    Luca_n (int)
  """
  luca = [0] * max((n + 1), 2)    
  luca[0] = 2
  luca[1] = 1
  for i in range(2, n+1):
    luca[i] = luca[i-1] + luca[i-2]
  return luca[n]
  



n = int(input())
print(calc_lucas(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[-1])

Solution (Python):
N = int(input())
prev, ans = 2, 1
for _ in range(N - 1):
    prev, ans = ans, ans + prev
print(ans)

Solution (Python):
memo = {0:2, 1:1}
def f(n):
  global memo
  if n in memo:
    return memo[n]
  else:
    res = f(n-1) + f(n-2)
    memo[n] = res
    return res

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

Solution (Python):
def lucas(n):
  if(n == 0):
    return 2
  if(n == 1):
    return 1
  if(n == 25):
    return 167761
  if(n == 26):
    return 271443
  if(n == 50):
    return 28143753123
  if(n == 51):
    return 45537549124
  if(n == 75):
    return 4721424167835364
  if(n == 76):
    return 7639424778862807
  return lucas(n- 1)+ lucas(n- 2)

N = int(input())

print(lucas(N))

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

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

Solution (Python):
N=int(input())
L_0 = 2
L_1 = 1
if N==0:
    print(L_0)
elif N==1:
    print(L_1)
else:
    for i in range (N-2):
        if i%2 ==0:
            L_0 = L_0 + L_1
        else:
            L_1 = L_0 + L_1
    print(L_0 + L_1)

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

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

print(L)

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

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

Solution (Python):
def ABC_79_B():
    N=int(input())
    l = [0 for _ in range(N*2)]
    l[0]=2
    l[1]=1

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

    print(l[N])

if __name__ == '__main__':

    ABC_79_B()

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

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

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

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

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

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

print(L[n])

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

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[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())
a=2
b=1
a1=2
a2=1
for i in range(n-1):
	a=a1+a2
	a1=a
	a2=b
	b=a
if n==1:
	a=1
print(a)

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

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

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())
if n == 1:
    print(1)
else:
    Li = 2
    Lj = 1
    cnt = 2
    while True:
        Lk = Li + Lj
        if cnt == n:
            print(Lk)
            break
        cnt += 1
        Li = Lj
        Lj = Lk

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

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

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

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

l = [2, 1]

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

print(l[-1])

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

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

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

print(l[-1])

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

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

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

Solution (Python):
n=int(input())
def Fib(n):
    a, b = 2, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
print(Fib(n+1))

Solution (Python):
from functools import lru_cache

N = int(input())

@lru_cache(maxsize=None)
def luca(n):
    if n == 0:
        return 2
    if n == 1:
        return 1

    return luca(n - 1) + luca(n - 2)

print(luca(N))

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

def dfs(x):
    memo = [0]*(x+1)
    def _dfs(x):
        if x == 0:
            return 2
        elif x == 1:
            return 1
        elif memo[x] != 0:
            return memo[x]
        else:
            memo[x] = _dfs(x-1) + _dfs(x-2)
            return memo[x]
    return _dfs(x)

print(dfs(N))

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

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

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

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

print(num[n])

Solution (Python):
from collections import deque
K = int(input())
l = deque([2, 1])
for _ in range(K):
  l.append(sum(l))
  ans = l.popleft()

print(l.popleft())

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

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

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

print(lis[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())
l0 = 2
l1 = 1
if n == 0:
    print(l0)
elif n == 1:
    print(l1)
elif n>= 2:
    ll = [l0, l1] + [0 for _ in range(n-1)]
    for i in range(2,n+1):
        ll[i] = ll[i-1] + ll[i-2]
    print(ll[n])

Solution (Python):
n = int(input())
memo = [2, 1]
if n == 1:
    print(memo[n])
    exit()
else:
    for i in range(1,n):
        tmp = memo[1]
        memo[1] = memo[0] + tmp
        memo[0] = tmp

print(memo[1])

Solution (Python):
import sys
sys.setrecursionlimit(10000)

N = int(input())
l=[-1]*(N+1)

def lyuka(x):
  if l[x] != -1:
    return l[x]
  if x == 0:
    return 2
  if x == 1:
    return 1
  lyu = lyuka(x-1) + lyuka(x-2)
  l[x] = lyu
  return lyu

print(lyuka(N))

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

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

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]

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

Solution (Python):
def inp():
    return(int(input()))


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


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


n = inp()
print(lucas(n))

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

n = [0] * (N+1)
for i in range(N+1):
    if i == 0:
        n[i] = 2
    elif i == 1:
        n[i] = 1
    else:
        n[i] = n[i-1] + n[i-2]

print(n[N])

Solution (Python):

N=int(input())
ans=[None]*(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
b =1

if N == 1:
    print(b)
else:
    for _ in range(1,N):
        c = b + a
        a = b
        b = c
    print(c)

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

a =2
b =1

if N == 1:
    print(b)
else:
    for _ in range(1,N):
        c = b + a
        a = b
        b = c

    else:
        print(c)

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

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

Solution (Python):
from functools import lru_cache

N = int(input())

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

Solution (Python):

N = int(input())
num2 = 2
num1 = 1
num = 1
tmp = 0
i = 2

while i <= N:
    num = num1 + num2
    tmp = num
    num2 = num1
    num1 = tmp
    i += 1
print(num)

Solution (Python):
n=int(input())
l1,l2=2,1

for i in range(n):
  l1,l2=l2,l1+l2
  
print(l1)

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

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 = [0] * 100
l[0] = 2
l[1] = 1

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

Solution (Python):
n=int(input())
lo=2
li=1
cou=0
import sys
if n==1:
    print(1)
    sys.exit()
if n==2:
    print(3)
    sys.exit()

for  i in range(n-1):

    cou=lo+li
    lo=li
    li=cou
   

print(cou)

Solution (Python):
import sys
import math
import itertools

n = int(input())
lucas = [
    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(lucas[n-1])

Solution (Python):
n=int(input())
 
a=2
b=1
s=0
 
if n==1:
  s=1
  n=2
 
for i in range(n-1):
  nn = a+b
  ans=nn
  a=b
  b=nn
 
if s==1:
  ans = 1
 
print(ans)

Solution (Python):
a=int(input())
L=2
L1=1
L2=0
for i in range(a):
  L2=L+L1
  L=L1
  L1=L2
print(L)

Solution (Python):


N=int(input())
Lm=2
Ln=1
Lo=2
if N==0:
	print(2)
elif N==1:
	print(1)
else:
	for i in range(N-1):
		Lo=Lm+Ln
		Lm=Ln
		Ln=Lo
	print(Lo)

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

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

Solution (Python):
n = int(input())
l1 = 2
l2 = 1

for i in range(1, n):
    l1, l2 = l2, l1 + l2

print(l2)

Solution (Python):
N = int(input())
L = [-1] * 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())

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

print(dp[-1])

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

a, b = 2, 1

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

print(a)

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

Solution (Python):
def Ryuka(n):
    L = [2,1]
    for i in range(n-1):
        L.append(L[len(L)-1]+L[len(L)-2])

    return L[len(L)-1]

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

if __name__ == "__main__":
    main()

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

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

print(ans)

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

print(l[-1])

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

l = [0]*87

l[0], l[1] = 2, 1

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

print(l[n])

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

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

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

Solution (Python):
import sys

input = sys.stdin.readline

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

if __name__ == '__main__':
    main()

Solution (Python):
import math
import copy

neko = 0
nuko = 0
n = int(input())
a = [0] * 100
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())

List = [2, 1]

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

print(List[N])

Solution (Python):
import sys
import math
import bisect

def main():
    n = int(input())
    A = [2, 1]
    while len(A) - 1 < n:
        A.append(A[-2] + A[-1])
    print(A[n])

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
L0,L1 = 2, 1
for _ in range(N-1):
    L0, L1 = L1, L0+L1
print(L1)

Solution (Python):

"""
Created on Thu May 14 01:22:46 2020

@author: shinba
"""

L = [2,1]

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

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

Solution (Python):
from functools import lru_cache

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

N = int(input())

print(lucas(N))

Solution (Python):
from functools import lru_cache

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

N = int(input())

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

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

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

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

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

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

Solution (Python):

import sys


def solve(N: int):
    L = [2, 1]
    for _ in range(100):
        L.append(L[-1]+L[-2])
    return L[N]



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    print(solve(N))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

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

Solution (Python):
A=int(input())
b0=2
b1=1
save=0
for i in range(A-1):
    save=b1
    b1=b0+b1
    b0=save
print(b1)

Solution (Python):
A = [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324, 228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636, 4106118243, 6643838879, 10749957122, 17393796001, 28143753123, 45537549124, 73681302247, 119218851371, 192900153618, 312119004989, 505019158607, 817138163596, 1322157322203, 2139295485799, 3461452808002, 5600748293801, 9062201101803, 14662949395604, 23725150497407, 38388099893011, 62113250390418, 100501350283429, 162614600673847, 263115950957276, 425730551631123, 688846502588399, 1114577054219522, 1803423556807921, 2918000611027443, 4721424167835364, 7639424778862807, 12360848946698171, 20000273725560978, 32361122672259149, 52361396397820127, 84722519070079276, 137083915467899403, 221806434537978679, 358890350005878082, 580696784543856761, 939587134549734843]
print(A[int(input())])

Solution (Python):

import sys

import fractions
import copy
import bisect
import math
import numpy as np
import itertools
from itertools import combinations_with_replacement


from operator import itemgetter
from sys import stdin

from operator import mul
from functools import reduce
from collections import Counter





j=0
k=0
n=3
r=1
a=[0]






"1行1つの整数を入力を取得し、整数と取得する"




"12 21 332 とか入力する時に使う"
"1行に複数の整数の入力を取得し、整数として扱う"

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

for i in number_list:
    print(number_list[i-1])

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'''
x=[]
y=[]
for i in range(N):
    x1, y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
print(x)
print(y)
"複数行に2数値を入力する形式 x座標とy座標を入力するイメージ"
'''

'''
mixlist=[]
for i in range(N):
    a,b=input().split()
    mixlist.append((int(a),b))
print(mixlist)
"複数行にintとstrを複合して入力するやつ，今回はリスト一つで処理している"
'''

'''



"正方行列にstr型の値を入力"
'''




'''
入力
1 2
4 5
7 8
出力結果
[[1, 2], [4, 5], [7, 8]]
'''
"列数に関して自由度の高いint型の値を入力するタイプの行列"


'''
table = [[int(i) for i in input().split()] for m in range(m)]

print(type(N))
print(N)
print(type(M))
print(M)

print(type(table))
print(table)
'''











'''
入力
1234
出力
1
[[1, 2, 3, 4]]
'''




'''
word_list= input().split(" ")
print(word_list[0])
"連続文字列の入力"
"qw er ty とかの入力に使う"
"入力すると空白で区切ったところでlistの番号が与えられる"
'''



'''
A, B, C=stdin.readline().rstrip().split()
print(A)
"リストではなく独立したstr型を入れるなら以下のやり方でOK"
'''




"aという変数に入っているものを大文字にして出力"

















'''
コンビネーションの組み合わせの中身を出力する形式
for i in itertools.combinations(brray, 2)
combinationsをpermutationsにすれば順列になる
今回なら(abc133B)
入力
1 2
5 5
-2 8
出力
[[1, 2], [5, 5], [-2, 8]]
もちろん一次元リストでも使えるし
何よりiもリストのように使えるので便利
'''


'''
def cmb(n,r):
    
    r= min(n-r,r)
    
    if r == 0: return 1
    over = reduce(mul, range(n, n-r, -1))
    
    
    

    under = reduce(mul, range(1, r+1))
    
    
    
    

    return over // under
    
    
    
    
a = cmb(n, r)

'''

'''
import itertools
from itertools import combinations_with_replacement

combinationについて
以下の違いを意識しよう
combinations() p, r 長さrのタプル列、ソートされた順で重複なし

combinations_with_replacement() p, r 長さrのタプル列、ソートされた順で重複あり


使用例 　　　　　　　　　　　                  出力　　
combinations('ABCD', 2)　　　　　　　　　　　　AB AC AD BC BD CD

combinations_with_replacement('ABCD', 2)　　 AA AB AC AD BB BC BD CC CD DD
'''



'''




for i in a.most_common(n):print(i)





 


'''









'''
bisect.bisect_left(a, x, lo=0, h=len(a))
引数
a: ソート済みリスト
x: 挿入したい値
lo: 探索範囲の下限
hi: 探索範囲の上限
(lo, hiはスライスと同様の指定方法)
bisect_leftはソートされたリストaに対して順序を保ったままxを挿入できる箇所を探索します。leftが示す通り、aにすでにxが存在している場合は、挿入箇所は既存のxよりも左側になります。また、lo, hiを指定することで探索範囲を絞り込むことも可能です。デフォルトはaの全体が探索対象です。
'''

'''
素数の判定
'''


def is_prime(n):
    if n == 1: return False

    for k in range(2, int(np.sqrt(n)) + 1):
        
        if n % k == 0:
            return False
            
    return True


'''
npのmaxとmaximumの違い
xs = np.array([1, -2, 3])
np.max(xs, 0)
この出力は3となります．[1, -2, 3]と0の4つの数字のうち，最も大きい値を出力します．

一方で，[max(1, 0), max(-2, 0), max(3, 0)]を出力したい時があります．
その時は，numpyのmaximum関数を用います．

xs = np.array([1, -2, 3])
np.maximum(xs, 0)  

'''

def factorial(x, mod=10**9+7):
    
    
    
    tmp = 1
    for i in range(1, x+1):
        tmp = (tmp * i) % mod
    return tmp
    '''
    Basically, when you do a**d % n, you actually have to calculate a**d, which could be quite large.
    But there are ways of computing a**d % n without having to compute a**d itself, and that is what pow does.
    '''











def main():

    w=1
    j=0
    k=0
    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[-1])
    
    
    
    
    
    DP = np.zeros(w+1, dtype=int)
    exdp=np.zeros((3,4)) 
    
    
    
        
        
    
    
        
        
    


    "1行1つの整数を入力を取得し、整数と取得する"
    
    
    "12 21 332 とか入力する時に使う"
    "1行に複数の整数の入力を取得し、整数として扱う"
    
    


    
    
    
    '''
    入力
    1234
    出力
    [1, 2, 3, 4]
    '''
    pin_l=["x" for i in range(10)]
    

    ls = ["a", "b", "c", "d", "e"]


    
    

    
    

    
    
    
    
    
    '''
    lsというリストの場合に、1つ飛びの値を取得したい場合には
    ls[::2]
    のようにします。こうすると、
    ["a", "c", "d"]と出力される
    '''

if __name__ == "__main__":
    main()

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())
A =[2,1]
if N < 2:
    print(A[N])
    exit()
for i in range(2,N+1):
    A.append(A[i-1]+A[i-2])
print(A[-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):
import sys
sys.setrecursionlimit(10000)
dp = {}
def lucas(n):
    if n in dp:
        return dp[n]
    if n == 0:
        dp[n] = 2
        return dp[n]
    if n == 1:
        dp[n] = 1
        return dp[n]
    dp[n] =  lucas(n-1)+lucas(n-2)
    return dp[n]
N = int(input())
print(lucas(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[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]

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

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

a = 2
b = 1
if N == 0:
    print(a)
elif 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]
if n==1:
    print(l[1])
else:
    c = 2
    while(c<=n):
        l.append(sum(l[-2:]))
        c+=1
    print(l[-1])

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

llucas = [2, 1]

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

print(llucas[N])