~M = 1~

Just output ~1~.

~M = 2~

$$\displaystyle f(n) = \begin{cases}0 & \text{if }n \le 0 \\ 1 & \text{if }n = 1 \\ f(n-1) + f(n-3) & \text{otherwise}\end{cases}$$

~M = 3~

This one's tricky:

$$\displaystyle \begin{align*} A(n) &= A(n-1) + B(n-2) + C_1(n-3) \\ B(n) &= A(n-2) + C_2(n-3) + D(n-1) + D(n-3) \\ C_1(n) &= A(n-2) + C_2(n) \\ C_2(n) &= A(n-1) + A(n-2) + C_2(n-3) + D(n-1) + D(n-3) \\ D(n) &= A(n) + B(n-1) \end{align*}$$

Base cases are all ~0~ except that ~A(1) = 1~. The answer to the problem is ~A(N)~.

A diagram would be useful here but I am too lazy to draw one, so I will describe in words what each function represents:

• ~A(N)~ is the number of ways to satisfy the conditions if you're at the beginning of a line of length ~N~, with every tile behind you already visited.
• ~B(N)~ is similar, but exactly one tile right behind you is unvisited.
• ~C_1(N)~ is similar, but exactly two tiles right behind you are unvisited.
• ~C_2(N)~ is similar, but in addition to those two tiles, there might be another group of two tiles behind them, and another two, and another two, etc. Also, there might be a group of one tile at the end of that whole chain.
• ~D(N)~ is similar to ~A(N)~, but you can choose whether to start at the first tile or the second.

Complexity: ~\mathcal O(N)~