Semafor

Πιθανότατα είστε εξοικειωμένοι με μια λεγόμενη οθόνη 7 τμημάτων που χρησιμοποιείται ευρέως για την απεικόνιση ψηφίων σε διάφορες ψηφιακές συσκευές, όπως ρολόγια ή αριθμομηχανές. Λόγω της απλότητας, της διαισθητικότητας και της αισθητικής του, αυτό το σχέδιο έχει γίνει αποδεκτό σε όλο τον κόσμο. Ωστόσο, ο νεαρός Matej τάσσεται κατά του σχεδιασμού των 7 τμημάτων και ισχυρίζεται ότι η ίδια λειτουργικότητα μπορεί να επιτευχθεί πιο αποτελεσματικά, χρησιμοποιώντας μόνο 5 τμήματα.

Σχεδίαση οθόνης ~5~ τμημάτων - τα τμήματα επισημαίνονται με γράμματα από το ~a~ έως το ~e~.

Ο Matej αποφάσισε να κάνει τα πρώτα του επιχειρηματικά βήματα στον πιο ακμάζοντα κλάδο της κροατικής οικονομίας, το ποδόσφαιρο. Το επαναστατικό του σχέδιο θα χρησιμοποιηθεί σε πίνακες αλλαγών κατά τη διάρκεια των αγώνων της ~1.\,HNL~, της \(1^{ης}\) κατηγορίας του επαγγελματικού κροατικού ποδοσφαίρου. Αυτή τη στιγμή κάνει παρουσίαση για το διοικητικό συμβούλιο της Κροατικής Ομοσπονδίας Ποδοσφαίρου.
Ο πίνακας αλλγαών αποτελείται από ~M~ οθόνες ~5~ τμημάτων που, από αριστερά προς τα δεξιά, αντιπροσωπεύουν τα ψηφία του αριθμού της φανέλας που φοράει ο παίκτης που πρόκειται να φύγει από το γήπεδο. Στην αρχή της παρουσίασης του Matej, ο πίνακας αλλαγών αντιπροσωπεύει τον αριθμό ~X~ και ο Matej θα κάνει μία από τις παρακάτω κινήσεις κάθε δευτερόλεπτο:

• Θα ενεργοποιεί ένα τμήμα που είναι απενεργοποιημένο αυτήν τη στιγμή.
• Θα απενεργοποιεί ένα τμήμα που είναι ενεργοποιημένο αυτήν τη στιγμή.

Συνολικά, ο Matej θα κάνει ~N~ κινήσεις και θα φροντίζει ώστε μετά από κάθε ~K~-οστή κίνηση, ο πίνακας να δείχνει έναν έγκυρο αριθμό. Ο αριθμός είναι έγκυρος εάν κάθε ψηφίο του εμφανίζεται σωστά στην αντίστοιχη οθόνη (δηλαδή τα τμήματα που είναι ενεργοποιημένα εμφανίζουν ένα έγκυρο ψηφίο). Επίσης, οι αριθμοί που έχουν λιγότερα από ~M~ ψηφία είναι έγκυροι αν περιέχουν τον κατάλληλο αριθμό μηδενικών στην αρχή.
Για κάθε τελική κατάσταση (ακέραιος μεταξύ ~0~ και ~10^M - 1~), ο Matej ενδιαφέρεται να μάθει με πόσους διαφορετικούς τρόπους θα μπορούσε να κάνει τις κινήσεις του κατά τη διάρκεια της παρουσίασης έτσι ώστε να επιτευχθεί αυτή η τελική κατάσταση στο τέλος. Φυσικά, αυτός πρέπει να τηρεί όλους τους περιορισμούς που παρουσιάστηκαν προηγουμένως. Θεωρούμε δύο ακολουθίες κινήσεων διαφορετικές αν, υποθέσουμε ότι εκτελούνται σε δύο διαφορετικούς πίνακες ταυτόχρονα και υπάρχει μια στιγμή που οι δύο πίνακες αντιπροσωπεύουν μια διαφορετική κατάσταση. Δεδομένου ότι ο αριθμός των διαφορετικών τρόπων μπορεί να είναι αρκετά μεγάλος, σας ζητείται να τον υπολογίσετε modulo ~10^9 + 7~.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους ~M,\,N,\,K\;(1 \le K \le N)~ και ~X\;(0 \le X < 10^M)~ από την περιγραφή του προβλήματος.

Έξοδος

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

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	6	~M = 1,\,1 \le N \le 12~
2	15	~M = 1,\,1 \le N \le 10^{15}~
3	12	~M = 2,\,1 \le N \le 1\,500,\,K = N~
4	12	~M = 2,\,1 \le N \le 10^{15},\,1 \le K \le 15~
5	15	~M = 2,\,1 \le N \le 10^{15},\,1 \le K \le 1\,500~
6	40	~M = 2,\,1 \le N \le 10^{15}~

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

input

1 2 1 5

output

0
0
0
1
0
2
0
0
0
0

Επεξήγηση 1ου παραδείγματος

Στην αρχή της παρουσίασης ο (μονοψήφιος) πίνακας αλλαγών δείχνει τον αριθμό ~5~. Μετά από κάθε κίνηση (λόγω ~K = 1~), ο πίνακας πρέπει να εμφανίζει έναν έγκυρο αριθμό. O Matej πρόκειται να κάνει συνολικά ~N = 2~ κινήσεις. Επομένως, στο τέλος της παρουσίασης, ο πίνακας μπορεί να δείξει είτε τον αριθμό ~3~ είτε τον αριθμό ~5~. Ο αριθμός ~3~ μπορεί να ληφθεί με έναν τρόπο ~(5 - 9 - 3)~ και ο αριθμός ~5~ μπορεί να ληφθεί με δύο τρόπους (~5 - 9 - 5~ και ~5 - 8 - 5~).

input

1 3 3 8

output

0
0
0
6
0
13
0
0
0
0

input

1 4 2 4

output

24
0
8
0
37
0
4
28
4
24