f (pos, ones) = # способов дойти до позиции pos и иметь ones нулей на конце
f (pos, 1) = f (pos - 1, 0)
f (pos, 2) = f (pos - 1, 1)
f (pos, 0) = f (pos - 1, 0) + f (pos - 1, 1) + f (pos - 1, 2)

g (pos) = # способов с 0 на конце
g (pos) = g (pos - 1) + g (pos - 2) + g (pos - 3)
            + "0"         + "10"        + "110"
Ответ: g (n + 1)