Problem: 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.

Examples

Input

5


Output

11


Input

86


Output

939587134549734843

Solution (in PYTHON):

Solution:
import sys

DBG_FLAG = 0

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

# TIME OVER
# def lucas_num(num):
#     if num == 0:
#         luca = 2
#     elif num == 1:
#         luca = 1
#     else:
#         luca = lucas_num(num-1)+lucas_num(num-2)

#     return luca

def lucas_num(num):
    array = []
    array.append(2) # i=0
    array.append(1) # i=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]

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

print lucas_num(num)