Fibonacci Sequence

Background

In the world of mathematics, the Fibonacci sequence is a very famous series. It is known for its unique recursive definition and has wide applications in nature and computer science.

Problem Description

The Fibonacci sequence is a famous bit of mathematics, and it happens to have a recursive definition. The first two values in the sequence are $0$ and $1$ (essentially $2$ base cases). Each subsequent value is the sum of the previous two values, so the whole sequence is: $0, 1, 1, 2, 3, 5, 8, 13, 21$ and so on. Define a recursive fibonacci(n) method that returns the $n$-th Fibonacci number, with $n=0$ representing the start of the sequence.

Input Format

The input is given from standard input in the following format.

$n$

Output Format

Output to standard output in the following format.

Fibonacci number

Sample

0

0

1

1

2

1

Sample Explanation

For Sample 1, when $n=0$, the $0$-th Fibonacci number is $0$. For Sample 2, when $n=1$, the $1$-st Fibonacci number is $1$. For Sample 3, when $n=2$, the $2$-nd Fibonacci number is $F_2 = F_1 + F_0 = 1 + 0 = 1$.

Constraints

Time limit: $1$ second, Memory limit: $1024$ KiB for each test case.