Construction of Iterative( Bottom up ) solution from Recursive( Top down ) solution

                                                               Tetrahedron

You are given a tetrahedron. Let's mark its vertices with letters A, B, C and D correspondingly.

An ant is standing in the vertex D of the tetrahedron. The ant is quite active and he wouldn't stay idle. At each moment of time he makes a step from one vertex to another one along some edge of the tetrahedron. The ant just can't stand on one place.

You do not have to do much to solve the problem: your task is to count the number of ways in which the ant can go from the initial vertex D to itself in exactly n steps. In other words, you are asked to find out the number of different cyclic paths with the length of n from vertex D to itself. As the number can be quite large, you should print it modulo 1000000007 (109 + 7).

Input

The first line contains the only integer n (1 ≤ n ≤ 107) — the required length of the cyclic path.

Output

Print the only integer — the required number of ways modulo 1000000007 (109 + 7).

Examples

input

2

output

3

input

4

output

21

Note

The required paths in the first sample are:

• D - A - D
• D - B - D
• D - C - D

Consider this problem , you have to calculate the number of path an ant start his journey from

vertex D and also end his journey at vertex D after n steps.

Solution

Case1:

If Ant is at vertex D and remaining steps are X , from this position ant only go to vertex A , B , C

so the Paths( D , X ) = Path( A , X - 1 ) + Path( B , X - 1 ) + Path( C , X - 1 ).

But wait and think little more 🤔

The vertex A , B , C they all are equal for D because it take only 1 steps from D to any of vertex

(A , B , C ).

Now , Let denote Vertex D = 1 and other vertices = 0.

So Path(1 , X) = 3 * Path( 0 , X -1 )

Case 2:

If ant is on any vertex other than D then Path( 0 , X ) = Paths from D + Paths from remaining 

two vertices.

So Path( 0 , X ) = Path(1 , X -1) + 2 * Path( 0 , X - 1) 

Recursive

Recurrence 

if( Ant is at 1(means at D) and remaining steps = X )

then ans = 3 * Path( 0 , X -1 )

else i.e not at D

then ans = Path(1 , X -1) + 2 * Path( 0 , X - 1) 

Base Case

if remaining steps is 0 then , 

• if current vertex == 1 (i.e D) then return 1 ( i.e one path found )
• else return 0 ( i.e. wrong path )

Memoize each steps

1. int Path( int left , int c , int dp[][2]){
2. if( left == 0 ){ // Base case
3. if( c == 1 )return 1;
4. else return 0;
5. }
6. if( dp[left][c] != -1 )return dp[left][c];
7. if( c == 1 ){// case 1
8. dp[left][c] = (3LL % Mod * Path( left - 1 , 0 , dp) % Mod) % Mod;
9. }
10. else{ // case 2
11. dp[left][c] = (2LL % Mod * Path(left - 1 , 0 , dp) % Mod 
12.                                             + Path(left - 1 ,1 , dp) % Mod) % Mod;
13. }
14. return dp[left][c];
15. }

Iterative

We will construct the iterative solution from the memoization solution in two simple steps:

1. (Easy step) Fill the base case entries in the array.
2. (Hard step) Fill the recursive case entries in the array.

1. Filling the base case entries

Base case entries are the ones where we can directly compute the answer, without further recursive calls.

Looking at the memoization solution , there left and c values , where left == 0 and 

c == 1 or c == 0

The code to fill base case entries will look like this:

1. dp[0][1] = 1; // left = 0 , c = 1
2. dp[0][0] = 0; // left = 0 , c = 0

2.Filling the Recursive case entries

Filling the Recursive case entries are the ones where we need recursive calls to compute the answer.

Once we rewrite the solution into iterative one, there will be no recursive calls. Instead, where the recursive call was before, we will directly use the values stored in the array:

1. for( int i = 1; i <= n; i++ ){
2.     // Note how we change Path(left - 1 , 0) to dp[i-1][0] and
3.     // path( left - 1 , 1 ) to dp[i-1][1]
4.     dp[i][1] = (3LL * dp[i-1][0]) % Mod;
5.     dp[i][0] = (2LL * dp[i-1][0] + dp[i-1][1]) % Mod;
6. }

What this means for us is that when we calculating the value of dp[i][1] and dp[i][0] , all the values of dp[j][1] and dp[j][0] ( for all j < i ) has been already calculated.

Full Solution

1. int dp[10000001][2];
2. 
   
3. int main(){
4.   int n;
5.   cin >> n;
6.   // fill base case entries :
7.   dp[0][1] = 1; 
8.   dp[0][0] = 1;
9.   // fill recursive case entries:
10.   // Iterate in the direction of increasing steps
11.   for( int i = 1; i <= n; i++ ){
12.     dp[i][1] = (3LL * dp[i-1][0]) % Mod;
13.     dp[i][0] = (2LL * dp[i-1][0] + dp[i-1][1]) % Mod;
14.   }
15.   cout << dp[n][1];
16. } 

Source of question