10403 - 斐波那契数列

斐波那契数列(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^{*})

请根据以上信息计算斐波那契数列中给定的某一项。

Input

Output

Examples

Input

2

Output

1

Input

5

Output

5
Time Limit 1000 毫秒
Memory Limit 128 MB
Stats
上一题 下一题