This was asked in a recent contest. The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same color. In other words, I want to count the number of different graph colorings of a grid graph: the graph of a $N \times M$ grid. The limits were $1 \le N,M \le 8$ and $1 \le K \le 1000000000$.
Is it possible to count the number of colors using the inclusion-exclusion principle, and if so, how? I saw another question that solves the special case (where $M=2$) using inclusion-exclusion, so I'm wondering if that kind of approach can be generalized here.