10005_Fibonacci数列

不知道Alice是从哪里听到Fibonacci数列，并对它发生了浓厚的兴趣。她想看看这个数列的递增过程是怎样的。

众所周知，Fibonacci数列的第一项是1，第二项也是1，从第三项开始，每项都是它前面两项之和。数列前面的一些项比较小，但增长速度很快，后面的项变得很大很大。

Alice虽然才一岁一个月，但显然不是一个简单的小朋友，她很可能需要第100项，甚至第500项等等。

嗯，这下就有点难度了吧。

大哥哥、大姐姐们，你能编一个程序，输出Fibonacci数列的第n项给Alice进行研究吗？

有多行，每行代表一个正整数n（1 ≤ n ≤ 1001）。

对每个输入，输出Fibonacci数列的第n项。

1
5
6
9
101

1
5
8
34
573147844013817084101

亲，别说第1001项了，请看看样例中的第101项有多大吧。