说明

斐波那契数列的定义如下：定义一组数的前两个数为 $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$ 的值

样例

8

21

数据范围

对于 60% 的数据，$1≤n≤50$；

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