WhiteBlue

Represent each column by an $N$-bit mask, using bit $0$ for white and bit $1$ for blue.

First retain only masks with no three equal consecutive bits. Let $V$ be this set and $K=|V|$. Since $N\le 8$, we have $K\le 68$. For each column, a selected mask must also agree with all prepainted cells.

Only the last two columns are needed to check the horizontal condition. Let $dp[a][b]$ count valid paintings of the processed prefix whose last two column masks are $a,b$. We may append mask $c$ exactly when, in every row, the corresponding three bits in $a,b,c$ are not all equal. Then add to , taking all values modulo .

If $M=1$, simply count the allowed masks for the first column. Otherwise initialize the DP using all allowed pairs of masks for the first two columns, process subsequent columns, and sum all final states.

Building the vertical-valid masks takes $O(N2^N)$ time, checking compatibility with fixed cells takes $O(MNK)$ time, and the DP takes $O(MK^3)$ time. Precomputing the transitions uses memory. Each addition combines two reduced residues, so it fits in a signed 32-bit integer.