斐波那契数列

题目背景

在数学世界中，斐波那契数列是一个非常著名的序列。它以其独特的递归定义而闻名，在自然界和计算机科学中都有广泛的应用。

题目描述

斐波那契数列是一个著名的数学序列，它具有递归定义。序列的前两个值是 $0$ 和 $1$（可以看作是两个基本情况）。序列中的每个后续值都是前两个值的和，因此整个序列是：$0, 1, 1, 2, 3, 5, 8, 13, 21$ 等等。 请定义一个递归方法 fibonacci(n)，该方法返回第 $n$ 个斐波那契数，其中 $n=0$ 代表序列的开始。

输入格式

输入以如下格式从标准输入中给出。

$n$

输出格式

输出以如下格式输出到标准输出中。

斐波那契数

样例

0

0

1

1

2

1

样例解释

对于样例1，当 $n=0$ 时，斐波那契数列的第 $0$ 个数是 $0$。 对于样例2，当 $n=1$ 时，斐波那契数列的第 $1$ 个数是 $1$。 对于样例3，当 $n=2$ 时，斐波那契数列的第 $2$ 个数是 $F_2 = F_1 + F_0 = 1 + 0 = 1$。

数据范围

每个测试用例的时间限制为 $1$ 秒，内存限制为 $1024$ KiB。