Piratski kod

Η Καπετάνισσα Μαρρρτίνα, μαζί με το πειρατικό της πλήρωμα, μετά από τρεις μήνες αναζήτησης για τον χαμένο θησαυρό που ανήκε στον πιο διάσημο Ιταλό πειρατή, ξέθαψε επιτέλους ένα σεντούκι γεμάτο θησαυρό. Αλλά για να ξεκλειδώσει το σεντούκι, χρειάζεται έναν μυστικό συνδυασμό που περιγράφεται σε ένα μήνυμα μέσα σε ένα μπουκάλι δίπλα από το σεντούκι.

Το μήνυμα λέει:

Για να μπορέσει μόνο ο πιο άξιος πειρατής να ανοίξει το σεντούκι με το θησαυρό, ο συνδυασμός είναι η λύση του ακόλουθου παζλ: Μια δυαδική ακολουθία ~s~ μήκους ~a~ στην οποία το μοναδικό ζεύγος διαδοχικών μονάδων βρίσκεται στο τέλος της ακολουθίας είναι μια πειρατική αναπαράσταση ενός αριθμού x εάν

~s[0] \ast Fib[2] + s[1] \ast Fib[3] + s[2] \ast Fib[4] + \ldots + s[a - 2] \ast Fib[a] = \sum_{i=0}^{a-2}s[i] \ast Fib[2 + i]= x~

όπου Fib[x] συμβολίζει τον ~x~-οστό αριθμό Fibonacci. Οι αριθμοί Fibonacci ορίζονται ως εξής: ~Fib[1] = 1~, ~Fib[2] = 1~, ~Fib[y] = Fib[y - 1] + Fib[y - 2]~ για κάθε ~y > 2~.

Για παράδειγμα, ~11_p = 1~, ~011_p = 2~, ~1010011_p = 17~, όπου ~_p~ υποδηλώνει μια πειρατική αναπαράσταση ενός αριθμού.

Ένας πειρατικός κώδικας είναι μια δυαδική ακολουθία (χωρίς καμία συνθήκη για διαδοχικές μονάδες) που αναπαριστά μια ακολουθία θετικών ακεραίων. Για να τον διαβάσουμε, τον διαμερίζουμε σε όσo το δυνατόν περισσότερα μέρη τα οποία είναι πειρατική αναπαράσταση κάποιου αριθμού (και πιθανώς κάποιο θα είναι ένα επίθεμα που δεν είναι πειρατική αναπαράσταση κανενός αριθμού) και γράφουμε αυτούς τους ακεραίους σε μια ακολουθία. Για παράδειγμα, διαιρούμε το ~01111010110101~ σε ~011|11|01011|0101~, όπου το τελευταίο μέρος δεν είναι πειρατική αναπαράσταση, οπότε το διαγράφουμε ~011|11|01011~ και διαβάζουμε μια ακολουθία ~2,\;1,\;7~.

Η τιμή ενός πειρατικού κώδικα είναι ίση με το άθροισμα των τιμών της αποκωδικοποιημένης ακολουθίας θετικών ακεραίων. Η τιμή του προηγούμενου κώδικα είναι ~10~.

Ο αγαπημένος μου αριθμός ~P~ είναι το άθροισμα των τιμών όλων των πειρατικών κωδικών μήκους ~k~. Ο αριθμός αυτός μπορεί να είναι πολύ μεγάλος και έτσι ο συνδυασμός για το σεντούκι θα είναι το υπόλοιπο του ~P~ modulo ~10^9 + 7~.

Leonarrrdo da Pisa

Αν η Μάρρρτινα δεν καταφέρει να ανοίξει το σεντούκι, το πλήρωμά της δεν θα τη θεωρήσει αρκετά άξια και θα την αναγκάσει να περπατήσει στο στενό σανίδι.

Είσοδος

Στην πρώτη και μοναδική γραμμή, θα υπάρχει ο θετικός ακέραιος ~n \le 5000~.

Έξοδος

Σε μια και μοναδική γραμμή εξόδου εκτυπώστε ~n~ αριθμούς, όπου ο ~k~-οστός αριθμός θα αντιπροσωπεύει την απάντηση στα παζλ για κωδικούς μήκους ~k~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~n = 20~
2	40	~n = 300~
3	50	~n = 5000~

Παραδείγματα

input

4

output

0 1 4 16

Διευκρινήσεις

Οι κωδικοί μήκους ~1~ είναι το ~0~ και το ~1~ όπου και τα δύο έχουν τιμή ~0~. Ο κωδικός ~11~ έχει τιμή ~1~ ενώ όλοι οι άλλοι κωδικοί μήκους ~1~ έχουν τιμή ~0~. Ο κωδικός ~1111~ έχει τιμή ~2~, ενώ ο κωδικός ~0011~ έχει τιμή ~3~.