题目描述

斐波那契数列的前几项为：$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$
从第三项起，每一项都是紧挨着的前两项的和。
请用递归函数计算斐波那契数列的第 $n$ 项。

输入格式

一行一个整数 $n$，表示要求的项数。

输出格式

一行一个整数，表示斐波那契数列第 $n$ 项的值。

样例

10

34

数据范围

• $1 \le n \le 30$（保证结果在 int 范围内）。