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 of length in which the only pair of consecutive ones is located at the end of the sequence is a pirate representation of a number if where denotes the -th Fibonacci number. Fibonacci numbers are defined as follows: for each .

For example , , , where 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 , , .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 .

My favourite number is the sum of values of all pirate codes of length . As that number may be large, the combination to the chest is the remainder of modulo

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

#### Output Specification

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

#### Constraints

Subtask | Points | Constraints |
---|---|---|

1 | 20 | |

2 | 40 | |

3 | 50 |

#### Sample Input 1

`4`

#### Sample Output 1

`0 1 4 16`

#### Explanation for Sample 1

Codes of length are `0`

and `1`

and they both have value .

The code `11`

has value while all other codes of length have value .

The code `1111`

has value , and the code `0011`

has value .

## Comments