I'm Sick of Fibonacci~

Interview

Time limit1sMemory limit512 MB

Summary

Given n, count the total number of calls made by the naive recursive Fibonacci function, modulo 1,000,000,007.

Level: Medium4 of 10
Topics: Dynamic programming, Recursion, Math, Implementation
Solved: No attempts yet

Problem

Hyeokjin is stressed out because he keeps being nagged to write an algorithm problem. But he has seen Fibonacci problems so many times that he is thoroughly sick of them. Since he has no time to write a problem, Hyeokjin decides to make one by adapting a Fibonacci problem.

int fibonacci(int n) { // call
  if (n < 2) {
    return n;
  }  
  return fibonacci(n-2) + fibonacci(n-1);
}

Given the code above, compute how many times the function fibonacci is called when fibonacci(n) is called.

Input

You are given n, the argument passed to the fibonacci function. (0 ≤ n ≤ 50)

Output

Print the number of times the fibonacci function is called.

The answer can be very large, so print it modulo 1,000,000,007.

Examples2

Example 1
Input
```
2
```
Expected output
```
3
```
Example 2
Input
```
3
```
Expected output
```
5
```