Fibonacci Sequence (fib)

Problem Background

Special for beginners, ^_^

Problem Description

The Fibonacci sequence $0,1,1,2,3,5,8,13,21,34,55\ldots$ is such that, starting from the third term, each term equals the sum of the two immediately preceding terms. Write a recursive program that computes any specified term of the Fibonacci sequence.

Input Format

The input is the index of the term to compute.

Output Format

Output the value of that term.

Sample Input

9

Sample Output

34

Constraints

Time limit: 1s, memory limit: 1024KiB for each test case.

All values are within the range of int.