题目描述

用递归函数输出斐波那契数列第 $n$ 项。斐波那契数列定义为：$F_0 = 0$，$F_1 = 1$，$F_n = F_{n-1} + F_{n-2}$（$n \ge 2$）。数列前几项为：$0, 1, 1, 2, 3, 5, 8, 13, \dots$

输入格式

一个正整数 $n$，表示第 $n$ 项。

输出格式

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

样例

3

1

数据范围

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