小鑫与斐波那契(一)

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

相信大家都知道斐波那契数列问题。但是小鑫不知道。(这是一个悲伤的故事)
在数学上,斐波纳契数列定义为:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)
你能帮小鑫算出第n个斐波那契数是多少么?

Input

输入数据为多组,到文件结束。
每组数据为一行一个数n。n<50;

Output

对于每组输入,输出一行,为答案。

Sample Input

1
2
3

Sample Output

1
1
2

Hint

 

Source

lin