菲波拉契数列

题目描述

求菲波拉契数列a0,a1,a2,……an。 a0=0，a1=1，a2=a1+a0，a3=a2+a1，……， an=an-1+an-2；如0,1,1,2,3,5,8,13,21,……，

求第n项菲波拉契数列的值。

输入

一行一个整数

输出

一行一个整数

样例测试

5

3

#数据范围

1s, 1<=n<=10^5