Hard Counting

Chef bought a rectangular checkered board of size $N$ rows and $M$ colums and color pens of $P$ different colors. He randomly painted each cell with any of the $P$ colors. When he was done painting all the cells, he noticed something very interesting property. For any vertical line that divides the board into two non-empty boards, the number of distinct colors in both the parts was the same. N