So how can I implement this idea? If yes, can you be more specific?

nevermind, read it wrong

Exponentiation of adjacency matrix for a graph of masks transitions? Nice.

Obviously, with the complexity of $$$O(N∗2^M)$$$

With the help of matrix exponentiation, our time complexity would be $$$O((2^M)^3∗logN)$$$

If I'm not missing anything, you need $$$2M$$$ (instead of $$$M$$$) bits to "remember" the state of 2 previous columns (each column having $$$M$$$ bits that represent state of board cells of that column), so there'll be $$$2^{(2M)} = 4^M$$$ instead of $$$2^M$$$ possible $$$mask$$$ values.

So the mentioned complexities will be more like $$$O(N∗4^M)$$$ and $$$O((4^M)^3∗logN)$$$ respectively.

However it seems that it's possible to improve from $$$4^M$$$ $$$mask$$$ states to $$$3^M$$$ states (for $$$M$$$ divisible by 4, other $$$M$$$ are left as an exercise to the reader). For $$$M=4$$$ if we enumerate the bits (state of board cells: 1 — there's a knight, 0 — there's no knight) of 2 last columns as follows:

$$$X_1 | X_2$$$

$$$X_3 | X_4$$$

$$$Y_2 | Y_1$$$

$$$Y_4 | Y_3$$$

We note that if $$$mask$$$ corresponds to correct filling of the board with knights, then for each $$$i$$$ each of $$$(X_i, Y_i) \neq (1, 1)$$$ (since knights on board cells $$$X_i, Y_i$$$ attack each other), so we can only have $$$(X_i, Y_i) = (0, 0) or (0, 1) or (1, 0)$$$ (3 possible values).

Also, it seems to me that with the first approach ($$$O(N∗2^M)$$$ in your analysis, $$$O(N∗4^M)$$$ in my analysis) the correct complexity should be $$$O(N∗M∗2^{2M+1})$$$ (if we use a messy approach where columns $$$i, i+2$$$ are partially filled, column $$$i+1$$$ is filled fully).

With the second approach (matrix exponentiation) (for $$$M$$$ divisible by 4), $$$O((3^M)^3∗logN)$$$ still seems achievable.