题目描述

小喵开始学习数列了。他学习到一种特别的数列——斐波那契数列。

我们都知道斐波那契数列的，数列如下：

$1~1~2~3~5~8...$ ，小喵想用递归求出该数列的第 $N$ 项是多少？你能编程帮他实现吗？

输入格式

一行一个整数 $N$ 。

输出格式

一行一个整数，输出斐波那契的第 $N$ 项。

样例输入

3

样例输出

2

数据范围

对于 $100\%$ 的数据： $1\le n\le 40$。