### PROBLEM LINK:

**Editorialist:** Karan Aggarwal

### DIFFICULTY:

EASY

### PREREQUISITES:

MATHS, MODULAR EXPONENTIATION

### PROBLEM:

Given infinite supply of K different types of explosives you have to find the number of ways to place the explosives in a grid of size N*2 such that :

Type[i][0] != Type[i][1],

Type[i][j] != Type[i+1][j]

### EXPLANATION:

There are K*(K-1) ways to fill the first row.

And for any other row, there are exactly (K-2)*(K-2) + 1*(K-1) ways to fill the row.

This can be calculated as follows.

Let say we are filling the ith row, and the (i-1)th row is such that Type[i-1][0] = a, Type[i-1][1] = b.

Now Type[i][0] can be any other color c different from a and b, hence there are (K-2) ways to chose c, and then Type[i][1] can be any color other than b and c, so again (K-2) choices. Hence (K-2)^{2} ways.

If we pick Type[i][0] = b, then we have (K-1) different ways to pick Type[i][1], since Type[i][0] = Type[i-1][1] = b. Hence (K-1) ways. So a total of (K-2)^{2} + (K-1)

Hence ANS[N] = K*(K-1) * ((K-2)^{2} + (K-1))^{(N-1)}

We can use fast modular exponentiation to calculate the answer for each test case in O(log(m)),