Stone Cold Mafia :
Difficulty Level : Easy
Submissions : 303
Asked In :
Marks :10
: 5 | : 1
Stone Cold is an American actor, producer, television host, and most importantly a famous professional wrestler. He has invented a new game which he named on himself - Stone Cold Mafia. In the game, you need to arrange his trophies on a tray. The size of tray is $$$N$$$ and the different types of trophies are $$$K$$$.
You want to place these trophies on the tray next to each other such that no trophy of the same type is sitting adjacent. Also, there is a special trophy $$$X$$$ which means trophies of type $$$X$$$ are allowed to place adjacent to each other.
Find the number of such possible arrangements mod $$$10^9 +7$$$
The first line of input consists of 3 space separated integers $$$-$$$ $$$N$$$, $$$K$$$ and $$$X$$$. $$$(1 \leq N \leq 10^5)$$$ $$$(1 \leq K, X \leq 5)$$$
The output should consist of a single integer $$$-$$$ the total number of such possible arrangements modulo $$$10^9+7$$$
3 2 1
5
5 4 3
469
You can assume that the number of trophies of each type is infinite and so you can you use as many trophies of each type in the arrangement. Also, X can be greater than K meaning that no there is no special trophy.
