piratski — COCI CONTEST_#5
Task type: batch | Time limit: 2 s | Memory limit: 512 MB | Difficulty: 20
Algorithms: string sequences, number theory, combinatorics, dynamic programming

# Task 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 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] \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}[x]$ denotes the $x$-th Fibonacci number. Fibonacci numbers are defined as following: $\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 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.

#### Input

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

#### Output

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

## Scoring

| Subtask | Points | Constraints |
|---------|--------|-------------|
| 1       | 20     | $n \le 20$    |
| 2       | 40     | $n \le 300$   |
| 3       | 50     | $n \le 5000$  |

### Examples

**input**

```
4
```

**output**

```
0 1 4 16
```

#### Clarification:

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

Code 11 has value 1 while all other codes of length 1 have value 0.

Code 1111 has value 2, and code 0011 has value 3.

Starter code: