P10259 [COCI 2023/2024 #5] Pirate Code

**Translated from [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) Task 3「[Piratski kod](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」**

Captain Marrrtina and her pirate crew, after searching for three months, finally dug up a chest containing the lost treasure of the most famous Italian pirate. However, to open the chest, she needs a password, described in a message inside a bottle next to the chest. The message says: --- Only the most worthy pirates can open the chest. The password is the answer to the following riddle: For a binary sequence $s$ of length $a$, where the only occurrence of two consecutive $1$ bits is at the end of the sequence, it is a pirate representation of a number $x$ if it satisfies: $$ s[0]\cdot \text{Fib}[2] + s[1]\cdot \text{Fib}[3] + s[2]\cdot \text{Fib}[4] + \ldots + s[a − 2]\cdot \text{Fib}[a] = \sum_{i=0}^{a-2} s[i]\cdot \text{Fib}[2 + i] = x $$ Here $\text{Fib}[x]$ is the $x$-th Fibonacci number. Fibonacci numbers are defined as $\text{Fib}[1] = 1$, $\text{Fib}[2] = 1$, and for each $y > 2$, $\text{Fib}[y] = \text{Fib}[y − 1] + \text{Fib}[y − 2]$. For example, $11_p = 1$, $011_p = 2$, $1010011_p = 17$, where $p$ denotes the pirate representation of a number. A pirate code is a binary sequence (with no restriction about consecutive $1$'s) that represents a sequence of positive integers. To read it, we split it into as many parts as possible, where each part is a pirate representation of some number (and there may be a suffix that is not a pirate representation of any number), and then we write down those integers in order. For example, we split $01111010110101$ into $011|11|01011|0101$. The last part is not a pirate representation, so we discard it and obtain $011|11|01011$, which is read as the sequence $2,1,7$. The value of a pirate code equals the sum of the decoded positive integers. The value of the above password is $10$. My favorite number $P$ is the sum of the values of all pirate codes of length $k$. Since this number can be very large, the password to open the chest is the remainder of $P$ when divided by $10^9 + 7$. — *Leonarrrdo da Pisa* --- If Marrrtina cannot open the chest, her crew will consider her untrustworthy and force her to walk the plank.

One line contains one integer $n\ (n\le 5\ 000)$.

Output one line with $n$ integers. The $k$-th integer should be the answer to the password riddle for length $k$.

### Sample Explanation 1 The codes of length $1$ are $0$ and $1$, and both have value $0$. The code $11$ has value $1$, and all other codes of length $2$ have value $0$. The code $1111$ has value $2$, and the code $0011$ has value $3$. ### Subtasks | Subtask | Points | Constraints | | :--: | :--: | :--: | | 1 | 20 | $n=20$ | | 2 | 40 | $n=300$ | | 3 | 50 | $n=5000$ | Translated by ChatGPT 5