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:
#!/user/bin/python
# coding: UTF-8

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]