Find the number of ways to colour an N x M grid using K colours. Adjacent squares in the grid should have different colours.
Constraints are as follows 1 <= N,M,K <= 10000. Print the solution modulo 1e9 + 7.
The same question with different constraints can be found here. I also found an unanswered question here on codechef 
I was only able to solve this question when either N or M is 1 or K is 2.(Pretty easy for these cases)