Pirate Code

Captain Marrrtina and her pirate crew spent three months searching for the long lost treasure of the most famous Italian pirate, and finally dug up a chest full of gold. To unlock the chest, she needs a secret combination. It is described in a message in a bottle next to the chest.

The message says:

So that only the most worthy pirate can open the chest, the combination is the solution to the following puzzle. A binary sequence $s$ of length $a$ in which the only pair of consecutive ones is at the end of the sequence is a pirate representation of a number $x$ if

$\sum_{i=0}^{a-2} s[i] \cdot Fib[2+i] = x$

where $Fib[x]$ denotes the $x$-th Fibonacci number. Fibonacci numbers are defined by $Fib[1] = 1$, $Fib[2] = 1$, and $Fib[y] = Fib[y-1] + Fib[y-2]$ for each $y > 2$.

For example, $11_p = 1$, $011_p = 2$, $1010011_p = 17$, where $p$ denotes a pirate representation of a number.

A pirate code is a binary sequence (with no restriction on consecutive ones) that represents a sequence of positive integers. To read it, split it into as many parts as possible, where each part is a pirate representation of some number. A suffix that is not a pirate representation of any number may be left over, and it is discarded. The integers of the parts are then written in order. For example, split $01111010110101$ into 011|11|01011|0101. The last part is not a pirate representation, so it is dropped, leaving 011|11|01011, which reads as the sequence $2$, $1$, $7$.

The value of a pirate code is the sum of the values of the decoded sequence of positive integers. The value of the code above is $10$.

My favourite number $P$ is the sum of the values of all pirate codes of length $k$. Since that number may be large, the combination to the chest is the remainder of $P$ modulo $10^9 + 7$.

If Marrrtina does not open the chest, her crew will not consider her worthy and will make her walk the plank.

• Leonarrrdo da Pisa

A single line contains a positive integer $n \le 5000$.

Print $n$ numbers on a single line, where the $k$-th number is the answer to the puzzle for codes of length $k$.

Codes of length $1$ are $0$ and $1$, and both have value $0$.

Code $11$ has value $1$, and all other codes of length $1$ have value $0$.

Code $1111$ has value $2$, and code $0011$ has value $3$.