# PROBLEM LINKS

# DIFFICULTY

Simple

# PRE-REQUISITES

Recurrences, Simple Math

# Problem:

Chef is cooking two dishes, each one takes **N** processes to be prepared. Chef has **K** equipments which allow for **K** processes to be done at a given moment.

Chef has to cook two dishes in parallel.

This means that if the first dish is prepared by applying processes **A _{1}, A_{2}, A_{3}, … A_{N}** in this order, and the second dish made by processes

**B**, then

_{1}, B_{2}, B_{3}, … B_{N}**A**, because otherwise chef would need two equipments for the process A

_{i}!= B_{i}for any 1 <= i <= N_{i}. Also, no two consecutive processes are the same for each individual dish. That is, A

_{i}!= A

_{i+1}and B

_{i}!= B

_{i+1}.

Knowing this, please report the number of ways in which in which he can prepare the two dishes. Since the number of ways can be very huge, you have to report it modulo 1000000007.

# Explanation:

Let us fill in values for the processes for A and B simultaneously from i = 1 to N. For i = 1, there are K choices for A_{1} and K-1 choices for B_{1}. For a general other i, when we fill in A_{i} and B_{i}, we wish only that A_{i} != A_{i-1}, B_{i} != B_{i-1} and A_{i} != B_{i}.

So, there seem to be K-1 choices for A_{i} != A_{i-1} and similarly for B_{i}. but we haven’t ensured that A_{i} != B_{i}. We have to still subtract from these (K-1)^2 choices, those where the two are equal to each other, but aren’t equal to the previous two. There are K-2 choices for the them not being equal to the previous two, and for each of these choices, by setting A_{i} and B_{i} to this value, we get such a bad case. Thus the total number of ways of getting from i-1 to i, is (K-1)^2 - (K-2).

Another way of arriving at the above is, let us first fill in A_{i} and then B_{i}. We have two cases:

Case 1: A_{i} != B_{i-1} and A_{i-1} : there are K-2 cases.

Given this, B_{i} != B_{i-1} as well as A_{i}, hence there are K-2 choices for B_{i}.

Case 2: A_{i} = B_{i-1}. This already gives us that A_{i} != A_{i-1}. There is 1 choice for this.

Given the above, B_{i} != B_{i-1} only (since its anyway equal to A_{i}). Thus, there are K-1 choices for B_{i}.

The above reasoning gives us that the number of choices for A_{i} and B_{i} are (K-2)^2 + K-1. Note that this is also what we had got earlier.

Thus, final answer = (K * (K-1)) * ((K-2)^2 + K-1)^(N-1).

**Remember to output this modulo 1000000007**.

Also, for full points, we have that an O(N) method to find powers is too slow. In order to find powers in O(logN) time, we use the “logarithmic exponentiation” method.

### Logarithmic Exponentiation

Let us have a function f(a, b) that returns a^b modulo MOD (where MOD = 1000000007).

Then, since a^(b) = (a^2)^[b/2] * a^(b 2), we have
f(a, b) = (f((a*a) MOD, b/2) * (b&2 == 1? a : 1)) % MOD;

In the above, we necessarily need that a and b are “long long” (or 64-bit datatypes), else it will overflow an int.

The above method gives us an O(logN) time method to find powers.

# Partial Solutions for subtasks:

### Subtask 1:

With inputs as small as N, K <= 5, we know that the answer is only atmost about 600000, so iterating recursively over all possibilities should also work.

Let f(pos, a, b) := While filling in values from 1 to N, we are at pos, and we have A_{pos-1} = a, and B_{pos-1} = b.

Then, f(pos, a, b) = sum {f(pos+1, c, d): c != a, d != b, c != d, 1<= c, d <= K},

with base cases f(N+1, a, b) = 1,

and the final answer as f(1, 0, 0).

With a DP, the above can be done in O(N * K^4) even.

In fact, the crucial point to note is that f(pos, a, b) really does not depend on the values of a and b. Just that fact that a != b, and the symmetry in all the values would imply that we could just go from pos to pos+1 in each step, which is the essential idea for the full 100, or even for the O(N) approach in subtasks 2 and 3.

### Subtask 2:

This just uses an O(N) approach to find the answer.

The reasoning for this is as described in the Explanation section, except that we don’t bother about MOD, or about O(logN) exponentiation.

### Subtask 3:

Here, we need to take care of the value not crossing MOD. Things like integer overflows etc should be handled.

# Overflow Bugs:

For those who are not used to this arcane “answer modulo 1000000007”, you might be wondering what is going on.

The computer stores integers in 32 bits (int datatype) or 64 bits (long long in c++, long in Java). This means, that for an int, the bounds are:

(1 bit for sign and 31 bits for numbers) = -2^31 to 2^31-1. But what is 2^31?

2^31

= 2 * 2^30

= 2 * (2^10)^3

~ 2 * (10^3)^3

= 2 * 10^9.

So, if you are adding two numbers < MOD, you won’t overflow int. But what if you do

x = (a+b+c) % MOD? Here, a, b and c can go to about 10^9, and then adding all three may go unto 3*10^9, which can overflow int.

For such cases, you would rather use 64 bit integers.

Again, what would the range be for 64 bits integers?

(1 for sign and 63 for numbers) = -2^63 to 2^63-1. AndÉ

2^63

= 2^3 * 2^60

= 8 * (2^10)^6

~ 8 * (10^3)^6

= 8 * 10^18

Now, since MOD is about 10^9, by multiplying two numbers < MOD, you can still be within the range of a 64bit integer. But now, you will need to *immediately* take “% MOD”, else further multiplications will have errors.

For example, in this problem, using:

```
x = (x*((k-1)+(k-2)*(k-2)))%MOD; // Even though x, k and MOD are 64 bit integers, this is WRONG. Why?
```

To see why its wrong, just : substitute worst-case (i.e. largest) values into the variables and see if its overflowing even the 64bit datatype anywhere.

### On % operator

One more thing to note about "" operator, is that if (x < 0) then (x MOD) will also be < 0. So, if you needed to find (a-b) modulo MOD, you would not do

`x = (a-b) % MOD // this may give you a value < 0`

but instead

```
x = ((a-b)%MOD + MOD) % MOD
```