Let $m,n\geq2$ be natural numbers and consider the grid having $m$ rows and $n$ columns (in total, there are $mn$ points). Let us color each point black or white, but making sure that there are no equichromatic rectangles; i.e. rectangle whose four corners are of the same color. In how many different ways can we color the grid with the above condition satisfied?
If we denote this number by $P(m,n)$, then for example, $P(2,2)=2^4-2=14$. The original question I have been struggling with, asks to compute $$P(2,6)+P(3,6)+P(4,6)+P(5,6)+P(6,6)\,(\text{mod }1000)$$ but I don't have a clue. Any suggestions?