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 a 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:

So 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 $${\displaystyle s[0]\cdot \text{Fib}[2]+s[1]\cdot \text{Fib}[3]+s[2]\cdot \text{Fib}[4]+\dots +s[a-2]\cdot \text{Fib}[a]=\sum _{i=0}^{a-2}s[i]\cdot \text{Fib}[2+i]=x,}$$ where $\text{Fib}[y]$ denotes the $y$-th Fibonacci number. Fibonacci numbers are defined as follows: $\text{Fib}[1]=1,\text{Fib}[2]=1,\text{Fib}[y]=\text{Fib}[y-1]+\text{Fib}[y-2]$ for each $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 (without any conditions on consecutive ones) that represents a sequence of positive integers. To read it, we partition it into as many parts as possible, such that each part is the pirate representation of some number (and possibly a suffix that is not a pirate representation of any number) and write those integers in a sequence. For example we partition 01111010110101 into 011|11|01011|0101, the last part is not a pirate representation so we delete it, resulting in 011|11|01011, and read the sequence $2$, $1$, $7$.

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

My favourite number $P$ is the sum of values of all pirate codes of length $k$. As that number may be 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.

Input Specification

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

Output Specification

In a single line of output print $n$ numbers where the $k$-th number represents the answer to the puzzle for codes of length $k$.

Constraints

Subtask	Points	Constraints
1	20	$n=20$
2	40	$n=300$
3	50	$n=5000$

Sample Input 1

4

Sample Output 1

0 1 4 16

Explanation for Sample 1

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

The code 11 has value $1$ while all other codes of length $1$ have value $0$.

The code 1111 has value $2$, and the code 0011 has value $3$.