Piratski kod

문제

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:

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 $ss$ of length $aa$ in which the only pair of consecutive ones is located at the end of the sequence is a pirate representation of a number $xx$ if $$s[0]\cdot Fib[2]+s[1]\cdot Fib[3]+s[2]\cdot Fib[4]+\cdots +s[a-2]\cdot Fib[a]=\sum _{i=0}^{a-2}s[i]\cdot Fib[2+i]=x\text{,}s[0]\; \backslash cdot\; Fib[2]\; +\; s[1]\; \backslash cdot\; Fib[3]\; +\; s[2]\; \backslash cdot\; Fib[4]\; +\; \backslash dots\; +\; s[a\; -\; 2]\; \backslash cdot\; Fib[a]=\; \backslash sum\_\{i=0\}^\{a-2\}\{s[i]\; \backslash cdot\; Fib[2+i]\}\; =\; x\backslash text\{,\}$$ where $Fib[x]Fib[x]$ denotes the $xx$-th Fibonacci number. Fibonacci numbers are defined as following: $Fib[1]=1Fib[1]\; =\; 1$, $Fib[2]=1Fib[2]\; =\; 1$, $Fib[y]=Fib[y-1]+Fib[y-2]Fib[y]\; =\; Fib[y\; -\; 1]\; +\; Fib[y\; -\; 2]$ for each $y>2y\; >\; 2$.

For example ${11}_p=111\_p\; =\; 1$, ${011}_p=2011\_p\; =\; 2$, ${1010011}_p=171010011\_p\; =\; 17$, where $pp$ 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 $0111101011010101111010110101$ in $011\mathrm{\mid }11\mathrm{\mid }01011\mathrm{\mid }0101011|11|01011|0101$, the last part is not a pirate representation so we delete it $011\mathrm{\mid }11\mathrm{\mid }01011011|11|01011$ and read a sequence $22$, $11$, $77$.

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 $1010$.

My favourite number $PP$ is the sum of values of all pirate codes of length $kk$. As that number may large, the combination to the chest is the remainder of$$P modulo ${10}^9+710^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.

입력

In first and only line there is a positive integer n ≤ 5000.

출력

In a single line of output print $nn$ numbers where $kk$-th number represents the answer to the puzzles for codes of length $kk$.

힌트

Clarification:

Codes of length $11$ are $00$ and $11$ and they both have value $00$.

Code $1111$ has value $11$ while all other codes of length $11$ have value $00$.

Code $11111111$ has value $22$, and code $00110011$ has value $33$.

4

0 1 4 16