Fibonacci数列

Time Limit: 1000 mSec

Memory Limit: 32768 KB

Description

1202年,意大利数学家斐波那契出版了他的《算盘全书》,在书中第一次提到了著名的Fibonacci数列,定义如下:

现在你的任务是求出Fibonacci数列的第n项。

Input

输入数据由多组数据组成。每组数据一行,仅一个整数,表示n的值。

Output

对于每组数据,输出仅一行,即Fibonacci数列的第n项。

我们保证输出的结果不会超过1000位数。

Sample Input

20

Sample Output

6765

Hint

Source

FZUPC 2005

提交代码