## COCI '23 Contest 5 #3 Piratski Kod

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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

4

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

There are no comments at the moment.