A new massive township is planned by ABC Corporation. The project is stylistically planned with picturesque secneries and is inspired by some Italian towns to make the houses colourful. There are ‘C’ different colours of paints available; each house is to be painted the same colour as their adjacent houses. Some houses are to be painted a different colour from their adjacent houses To mke the town atractive, it is decided to paint exactly “K” pair of adjacent houses with different colour. If the houses cannot painted for certain combinations of values for N, C, or K, then display ‘0’.

Example: N=3, C=2, K=3, whwre output will be 0. In this case, the number of colours available are 3, but there should be exactly 3 pairs of houses of different colours, which is not possible.

Example 1:

Input: 4->Value of N 2->Value of C 1->Value of K

Output: 6

Explanation: From the inputs given above: Number of houses: 4 Number of colours: 2 Number of pairs of adjacent houses that should have different colour: 1 Assume the colours available are ‘A’ and ‘B’. A,A,A,B A,A,B,B A,B,B,B B,B,A,A B,A,A,A B,B,B,A

There are 6 different ways to paint 4 houses such that exactly 1 pair of adjacent houses has different colours. Hence output is 6.

Example 2:

Input: 3->Value of N 2->Value of C 2->Value of K

Output: 2

Explanation: From the inputs given above: Number of houses: 3 Number of colours: 2 Number of pairs of adjacent houses that should have different colour: 2 Assume the colours available are ‘A’ and ‘B’. A,B,A B,A,B

There are 2 different ways to paint 3 houses such that exactly 1 pair of adjacent houses has different colours. Hence output is 2.