题目描述

现在是日本的 $11$ 月 $18$ 日。顺便说一下，$11$ 和 $18$ 是相邻的卢卡斯数。

给定一个整数 $N$。找出第 $N$ 个卢卡斯数。

这里，第 $i$ 个卢卡斯数 $L_i$ 定义如下：

• $L_0=2$
• $L_1=1$
• $L_i=L_{i-1}+L_{i-2} (i≥2)$

约束条件

• $1≤N≤86$
• 答案保证小于 $10^{18}$。
• $N$ 是整数。

输入

输入以以下格式从标准输入给出：

$N$

输出

输出第 $N$ 个卢卡斯数。

示例输入1

5

示例输出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$

因此，第 $5$ 个卢卡斯数是 $11$。

示例输入2

86

示例输出2

939587134549734843