### PROBLEM LINK:

**Author:** Aman Kumar Gupta

**Editorialist:** Aman Kumar Gupta

### DIFFICULTY:

EASY-MEDIUM.

### PREREQUISITES:

DP, Math, Matrix, Fast exponentiation.

### PROBLEM:

The number of ways you can mine a row of size **1 * n** using given types of bombs modulo **10^9+7**.

### EXPLANATION:

The first method which can be used is DP of course. It seems to be a classical DP problem.

So when the size of the row is 1 * 1, dp[1] = 0. When the size of the row is 1 * 2, dp[2] = 1 and similarly dp[3] = 1, where dp* refers to the ways in which the row of size **i** can be mined.

And from here upon, build the dp array as: dp* = (dp[i - 2] + dp[i - 3]) % 1000000007;

Finally dp[n] would be our answer.

But this will fail here because of the large constraint.

Now, suppose we have an equation like this: **[dp[0], dp[1], dp[2]] * M = [dp[1], dp[2], dp[3]]**, where **M** is a matrix of size 3 * 3, then we can say **[dp[0], dp[1], dp[2]] * M^2 = [dp[2], dp[3], dp[4]]**.

On generalizing, **[dp[0], dp[1], dp[2]] * M^(N - 2) = [dp[n - 2], dp[n - 1], dp[n]]** for **N > 2**

To find the matrix, consider the matrix cells unknown and multiply it with the dp array on the left and equate it with the RHS. Leaving the task upon you, the matrix will be:

0 0 1

1 0 1

0 1 0

Now **M^(n - 2)** can be found in **27 * log n** and after all the multiplications of the above equation, our answer will simply be **FinalArray[2] (the last element of our resulting array on the RHS).**

**Note:** You need to take care of taking modulo on every operation to avoid the overflow. See the solution for more references.

### AUTHORâ€™S SOLUTION:

Authorâ€™s solution can be found here.