Codersbit 2019 problem

I need help with a problem from Codersbit 2019 held on 1st September.

There are 4 persons W X Y Z and there is one ball. Each person can pass the ball to any one of the rest 3. Initially the ball is with W. What is the probability that after A number of passes the ball will land back at person W. If the probability is p/q the answer should be (p ^ q-1) mod (10^9 + 7).
0<= A <= 10^5

I believe that the value of p = 3 * (A-1) and q = 3 ^ A but was getting WA. What should be the correct approach to this?

You could use dp for these kind of problems. The number of chances that Person X has after A passes can be calculated from the state A-1 passes. Initialise a A x 4 dp array. dp[0][W] = 1. Since after 0 passes the ball remains with W. Then you could calculate the probability after 1st pass as,
dp[1][W] = dp[0][X] + dp[0][Y] + dp[0][Z]
dp[1][X] = dp[0][W] + dp[0][Y] + dp[0][Z]
dp[1][Y] = dp[0][X] + dp[0][W] + dp[0][Z]
dp[1][Y] = dp[0][X] + dp[0][Y] + dp[0][W]

Repeat these for all passes upto A. dp[A][W] is your answer.


No if u apply your formula then answer will always 1 / 3 see… Your formula wrong

So, this gives me the number of favorable outcomes i.e p. Dividing it by 3^q gives the correct answer. Thanks.