Captain Marrrtina, together with her pirate crew, after three months of searching for long lost treasure
belonging to the most famous Italian pirate finally dug up chest full of treasure. But to unlock the chest
she needs a secret combination which is described in a message in a bottle next to the chest.
The message says:
S
o that only the most worthy pirate shall be able to 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 located at the end of the sequence is a pirate representation of a number \(x\) if
\(s\)[0] · Fib[2] + \(s\)[1] · Fib[3] + \(s\)[2] · Fib[4] + . . . + \(s\)[\(a - 2\)] · Fib[\(a\)] =
\(a - 2\)
X
\(i=0\)
\(s\)[\(i\)] · Fib[\(2 + i\)] = x,
where Fib[\(x\)] denotes the \(x-th\) Fibonacci number. Fibonacci numbers are defined as following: Fib[1] =
1, Fib[2] = 1, 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 (without any condition on consecutive ones) that represents a sequence
of positive integers. To read it we partition it in as many parts as possible that are pirate representation
of some numbers (and possibly a suffix that is not a pirate entry of any number) and write those integers
in a sequence. For example we partition 01111010110101 in 011|11|01011|0101, the last part is not a pirate
representation so we delete it 011|11|01011 and read a sequence 2, 1, 7.
The value of a pirate code is equal to the sum of values of decoded sequnce of positive integers. The value
of previous code is 10.
My favourite number \(P\) is the sum of values of all pirate codes of length \(k\). As that number may large,
the combination to the chest is the remainder of \(P\) modulo \(10^{9} + 7\)
- Leonarrrdo \(da\) Pisa
If Marrrtina doesn’t manage to open the chest, her crew will not consider her worthy and they’ll make
her walk the plank.

Subtask 1 (20 points): \(n = 20\)

Subtask 2 (40 points): \(n = 300\)

Subtask 3 (50 points): \(n = 5000\)

In first and only line there is a positive integer \(n \le 5000\).

In a single line of output print \(n\) numbers where \(k-th\) number represents the answer to the puzzles for
codes of length \(k\).

생성자가 기록되지 않았습니다.

출처 COCI 2023/2024 Contest 5