No submission language available for this problem.

Background

Special for beginners, ^_^

Description

斐波那契数列 （Fibonaccisequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（LeonardoFibonacci）

用一句话概括来说，第 i 个数字为第 i - 1 个数字和第 i - 2 个数字之和。即 $a_i = a_{i-1} + a_{i-2}$

以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

输入 n，求斐波那契数列的第 n 项。

注意：请用递归完成

Format

Input

一行一个整数 n (0 < n ≤ 60)。

Output

输出斐波那契数列的第 n 项。

Samples

5

5

Limitation

1s, 1024KiB for each test case.