Escriu un algoritme recursiu que trobi el nombre en la posició N de la Successió de Fibonacci.
Recorda que la Successió de Fibonacci, comença per \(0\) i \(1\), i que calcula el següent nombre sumant sempre els dos anteriors (fins l'inifinit, o fins a \(N\) en el nostre cas).

Input Format

Un nombre N.

Constraints

No hi ha.

Output Format

El número de la successió de Fibonacci que ocupa la posició N.

Test Case 1

Input

0

Output

0

Test Case 2

Input

1

Output

1

Test Case 3

Input

2

Output

1

Test Case 4

Input

3

Output

2

Test Case 5

Input

4

Output

3

Test Case 6

Input

5

Output

5

Test Case 7

Input

6

Output

8

Test Case 8

Input

7

Output

13

Test Case 9

Input

8

Output

21

Test Case 10

Input

15

Output

610

Test Case 11

Input

25

Output

75025