我们都知道斐波那契数列的，数列如下，0 1 1 2 3 5 8……试用递归求出该数列的第N项是多少

输入格式

一个整数，表示要求的斐波那契数列第几项

输出格式

输出斐波那契数列的值

样例

样例输入

3

样例输出

1

来源

08函数与递归

数据范围与提示

• 时间限制：$1000mathrm{ms}$
• 空间限制：$256000mathrm{KB}$