#描述#
已知菲波那契数的定义：
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2) n>1的整数
根据输入数据中的n，输出第n项菲波那契数。

#格式#
##输入格式##
输入数据中含有一些整数n（0≤n≤46）。

##输出格式##
根据每个整数n，输出其第n项菲波那契数，每个数占独立一行。

#样例1#
##样例输入1##

5
6
7
8
9
40

##样例输出1##

5
8
13
21
34
102334155

#限制#
1000ms
32768KB

#提示#

#来源#
qianneng