Branching factors

When dealing with recursive functions, it sometimes makes sense to call the current function several times with different arguments. For example, if we would calculate the n-th Fibonacci number with a recursive function, that might look something like this:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Here, for each argument n, we make 2 recursive calls to the function fib with arguments n-1 and n-2.

Challenge - Recursive Fibonacci

Count the number of times the recursive Fibonacci function is called.

Input

The input contains a single integer n (0 ≤ n ≤ 20).

Output

The program should print the number of times the fib function was called.

Examples

Input	Output
0	1
1	1
2	3
5	15
6	25

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB