题目描述

斐波那契数列（Fibonacci sequence），又称黄金分割数列，以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0) = 0，F(1) = 1, F(n) = F(n - 1) + F(n - 2)（n ≥ 2，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用

重点： F(n) = F(n - 1) + F(n - 2)， F(0)=0，F(1)=1,

如果我想要求第n项斐波那契数列，那我应该如何求呢？(n<=40)

输入格式

输入一个整数 n

输出格式

输出斐波那契数列第n项

样例数据

input1

4

output1

3

input2

15

output2

610

数据规模与约定

n ≤ 40