Background背景

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

Input输入

给一个正整数n，表示斐波那契数列第n项。（1 ≤ n ≤ 80）

Output输出

斐波那契数列第n项的值。

Samples样例

3

2

6

8

19

4181

Limitation限制

1s, 1024KiB for each test case.