Background

Translated from COCI 2023/2024 Contest #5 Task 3「Piratski kod」

Problem Description

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.

Input Format

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

Output Format

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

4

0 1 4 16

Hint

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