Klavir

Στη νεαρή Alisa αρέσει να παίζει πιάνο χρησιμοποιώντας μόνο ένα δάχτυλο. Δυστυχώς, η Alisa δεν έμαθε ποτέ να παίζει πιάνο, έτσι το παίξιμό της είναι εντελώς τυχαίο. Πιο συγκεκριμένα, κάθε φορά που επιλέγει έναν τόνο για αναπαραγωγή, το κάνει ανεξάρτητα από όλους τους προηγούμενους τόνους και επιλέγει κάθε έναν από τους ~N~ τόνους με την ίδια πιθανότητα.

Η καλή της φίλη Mirta θέλει να ακούσει μια σύνθεση που περιέχει ~M~ διαδοχικούς τόνους, αλλά καθώς η Alisa παίζει πιάνο τυχαία, η Mirta δεν ξέρει πόσο καιρό θα πρέπει να περιμένει για να ακούσει μια σειρά από αυτούς ακριβώς τους τόνους ~M~. Βοηθήστε τη Mirta να προσδιορίσει τον αναμενόμενο αριθμό πατημάτων πλήκτρων για να ακούσει, για πρώτη φορά, την επιθυμητή σειρά διαδοχικών τόνων της. Επιπλέον, δεδομένου ότι η Mirta είναι ένα πολύ περίεργο κορίτσι, θέλει επίσης να γνωρίζει τον αναμενόμενο αριθμό πατημάτων πλήκτρων για κάθε πρόθεμα της επιθυμητής σειράς τόνων της.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N~, τον αριθμό των διαφορετικών τόνων πιάνου ~(1 \le N \le 100)~.
Η δεύτερη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~M~, το μήκος του επιθυμητού πίνακα ~(1 \le M \le 10^6)~.
Η τρίτη γραμμή εισόδου περιέχει τον πίνακα ~M~ των θετικών ακεραίων μεταξύ 1 και ~N~.

Έξοδος

Η i-οστή από τις ακόλουθες ~M~ γραμμές πρέπει να περιέχει τον αναμενόμενο αριθμό πατημάτων πλήκτρων, για να ακούσει η Mirta το πρόθεμα μήκους i της επιθυμητής σειράς τόνων, στη μορφή modulo ~10^9 + 7~ (δηλαδή, το υπόλοιπο της ακέραιας διαίρεσης του αριθμού με το ~10^9 + 7~).

Τα δεδομένα δοκιμής θα είναι τέτοια ώστε ο αναμενόμενος αριθμός πατημάτων πλήκτρων θα είναι πάντα ακέραιος.

Βαθμολογία

Σε παραδείγματα αξίας 64 πόντων συνολικά, θα ισχύει ~1 \le M \le 200~.

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

input

2
2
1 2

output

2
4

input

2
2
1 1

output

2
6

input

3
3
1 2 3

output

3
9
27