说明

斐波那契数列的定义如下：定义一组数的第一个为1，第二个为1，之后的每个数都是前两个数之和，将这样的一组数称

为斐波那契数。斐波那契数的前十个数是：1，1，2，3，5，8，13，21，34，55。

公式如下：

$$F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right. $$

请你求出 $F_n$的值

输入格式

输入只有一行，包括1个整数$n$

输出格式

输出只有一行$F_n$的值

样例

10

55

数据范围

对于 100% 的数据，$1≤n≤40$