Number of ways to fill a 2xN grid with M colors
You can use inclusion-exclusion. There are $M!/(M-N)!$ choices for the first row. Fix these choices. The number of choices for the second row in which $T$ specific columns are bad (but the row itself is good) is $(M-T)!/(M-N)!$. According to the inclusion-exclusion principle, the required number is
$$ \frac{M!}{(M-N)!} \sum_{T=0}^N (-1)^T \binom{N}{T} \frac{(M-T)!}{(M-N)!}. $$
I'll let you take it from here.