Algorithm Class - Fibonacci Number 2

Time limit1sMemory limit512 MB

Summary

For a given n, count the base-case calls of recursive Fibonacci and the loop iterations of the DP version, each modulo 1e9+7.

Level: Easy3 of 10
Topics: Math, Dynamic programming, Recursion, Combinatorics
Solved: No attempts yet

Problem

Seojun is again working as a teaching assistant for a dynamic programming class. Let us check through a problem whether the students understood what his father taught in class.

Today they learned algorithms that compute the n-th Fibonacci number using recursion and dynamic programming. Let us see how much faster dynamic programming is than recursion. Using the pseudocode below to compute the n-th Fibonacci number, print the number of times code1 and code2 are executed.

The pseudocode for the recursive Fibonacci number is as follows.

fib(n) {
    if (n = 1 or n = 2)
    then return 1;  # code1
    else return (fib(n - 1) + fib(n - 2));
}

The pseudocode for the dynamic programming Fibonacci number is as follows.

fibonacci(n) {
    f[1] <- f[2] <- 1;
    for i <- 3 to n
        f[i] <- f[i - 1] + f[i - 2];  # code2
    return f[n];
}

Input

The first line gives n (5 ≤ n ≤ 2 × 10^8).

Output

Print, on one line, the number of executions of code1 and code2 modulo 1,000,000,007.

Examples3

Example 1
Input
```
5
```
Expected output
```
5 3
```
Example 2
Input
```
30
```
Expected output
```
832040 28
```
Example 3
Input
```
45
```
Expected output
```
134903163 43
```