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)
All I have been able to figure out by now is that this uses dp.
We need to store a NxM array of polynomials. The polynomials are such that when the polynomial at dp[i][j] is evaluated with input K, this gives the answer for the number of ways to color a grid of size i x j with K colors.
Now I need to figure out how to build the dp array. Any help is appreciated
Also, links to similar questions here on codechef will help.
**Very Same Problem On Codechef with Editorial : - **
It doesn’t seem like the very same problem. Am I missing some very obvious transformation?