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.