# Problem Statement :

Bob has been given a triangular pyramid with its vertices marked as ‘O’, ‘X’, ‘Y’ and ‘Z’ and provided with another integer ’N’. In a single step, Bob can go to any adjacent vertices. Bob will always start from ‘O’ and has to return to ‘O’ after making exactly ’N’ steps.

Your task is to find out the number of ways he can take to complete his journey.

As the answer can be very large, return the answer by taking modulo with 1000000007.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

# Approach :

One observation we can make is that the number of ways to reach the position ‘X’ ={‘O’,’X’,’Y’,’Z’} in the current step is equal to the sum of the number of ways Bob is not at position ‘X’ in the previous steps.

1. We will initialize a 2-D array say DP [N+1] with 0, where N is the number of steps. DP[i][j] will store the number of ways to reach ‘i’ with ’N’ equal to ‘j’.

2. Here column 0 is for position ‘O’, 1 for ‘X’,2 for ‘Y’ and 3 for ‘Z’.

3. Set DP is qaul to 1.

4. Run a loop for 1 <= i <= N and do:

• Intialise an integer variable ‘TEMP’ = 0.
• Run a loop for 0 <= j <= 3 and do:
• DP[j][i] = DP[(j+1)%4][i-1] + DP[(j+2)%4][i-1] + DP[(j+3)%4][i-1] .

5. Return DP[N].

Time Complexity: O(N)
Space Complexity: O(N)

# Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.