I was giving hackerrank test for some company recently and came across the following question. I searched and found out that it's unsolvable(NP-hard) for the given constraint. Please let me know if you know how to solve this one.

Problem

Calculate the number of ways to color an N * M grid using K colors. Adjacent squares in the grid should have different colors. Squares are considered adjacent if they share an edge.

Constraint : 1<=N,W,K<=10^5

Thanks