Mate

Ο μικρός Mate πήρε δώρο από τους γονείς του μια σειρά από πεζά γράμματα από το αγγλικό αλφάβητο. Για να έχει τουλάχιστον κάποια χρήση ενός τόσο έξυπνου δώρου, αποφάσισε να το χρησιμοποιήσει για να βρει ρίμες όταν έγραφε το επόμενο τραγούδι του.

Για να βρει μια συγκεκριμένη ομοιοκαταληξία, ο Mate θέλει να επιλέξει μια λέξη μήκους D που τελειώνει με έναν πίνακα χαρακτήρων ​XY​, δηλαδή όπου το προηγούμενο από το τελευταίο γράμμα είναι ​X και το τελευταίο ​Y. Η διαδικασία επιλογής μιας λέξης από τον Mate συνίσταται στο να διαγράφει πρώτα μερικά γράμματα σε μια δεδομένη ακολουθία και στη συνέχεια να συγχωνέψει τα γράμματα που δεν διέγραψε σε μία λέξη. Θέλει να μάθει με πόσους διαφορετικούς τρόπους μπορεί να διαγράψει τα γράμματα ώστε να πληρεί τις δεδομένες προϋποθέσεις.

Η επιλογή δύο λέξεων θεωρείται διακριτή εάν τα σύνολα θέσεων των διαγραμμένων γραμμάτων είναι διαφορετικά.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει μια σειρά από πεζά γράμματα του αγγλικού αλφαβήτου ​S (2 ≤ |S| ≤ 2.000). Η δεύτερη γραμμή εισαγωγής περιέχει τον ακέραιο αριθμό ​Q (1 ≤ Q ≤ 500.000), τον αριθμό των διαφορετικών ομοιοκαταληξιών για τις οποίες ο Mate πρέπει να επιλέξει λέξεις. Κάθε μία από τις ακόλουθες γραμμές Q περιέχει τον ακέραιο αριθμό ​D (2 ≤ D ≤ |S|) και μια σειρά από πεζά γράμματα του αγγλικού αλφαβήτου ​XY​ από την εργασία.

Έξοδος

Η i-οστή γραμμή από τις Q πρέπει να περιέχει τον απαιτούμενο αριθμό τρόπων για την i-οστή ομοιοκαταληξία. Δεδομένου ότι αυτός ο αριθμός μπορεί να είναι αρκετά μεγάλος, εξάγετε την τιμή ως υπόλοιπο ακέραιας διαίρεσης με τον αριθμό 10⁹+7.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 40% των συνολικών πόντων, θα ισχύει |S| ≤ 50. Σε περιπτώσεις δοκιμής αξίας επιπλέον 40% των συνολικών πόντων, θα ισχύει |S| ≤ 200.

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

input

banana
3
2 na
3 ba
4 nn

output

3
0
1

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

Η λέξη μήκους 2 που τελειώνει με "na" μπορεί να ληφθεί με τους ακόλουθους τρόπους:
b a n a n a , b a n a n a, b a n a n ​a​.

input

malimateodmameitate
3
10 ot
7 aa
3 me

output

2
464
56