Herkabe

Ο δάσκαλος Herkabe αποφάσισε να κατατάξει ξανά τους μαθητές του. Αυτή τη φορά, θέλει η λίστα του να είναι και αισθητικά ευχάριστη, γι' αυτό αποφάσισε ότι παρόμοια ονόματα (αυτά που ξεκινούν με το ίδιο γράμμα ή ακολουθία γραμμάτων) πρέπει να είναι κοντά το ένα στο άλλο στη λίστα. Ως εκ τούτου, επινόησε τον ακόλουθο κανόνα:
Για κάθε δύο ονόματα στη λίστα που ξεκινούν με την ίδια ακολουθία γραμμάτων, όλα τα ονόματα μεταξύ τους στη λίστα πρέπει επίσης να ξεκινούν με αυτήν τη σειρά γραμμάτων.
Για παράδειγμα, σκεφτείτε τα ονόματα MARTHA και MARY (χαρακτήρες από μια όμορφη ιστορία). Και οι δύο ξεκινούν με την ακολουθία MAR, επομένως ονόματα που ξεκινούν με την ίδια ακολουθία (όπως το MARCO και το MARVIN) μπορούν να εμφανιστούν στο ενδιάμεσο (αλλά όχι το όνομα MAY, για παράδειγμα).
Σημειώστε ότι η λεξικογραφικά ταξινομημένη σειρά ικανοποιεί πάντα αυτόν τον κανόνα, αλλά σε καμία περίπτωση δεν είναι η μόνη έγκυρη σειρά. Το καθήκον σας είναι να προσδιορίσετε πόσες διαφορετικές παραγγελίες ικανοποιούν τον κανόνα, δηλαδή πόσες επιλογές έχει ο δάσκαλος Herkabe για τη λίστα κατάταξης του.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο ~N\;(3 \le N \le 3000)~, τον αριθμό των ονομάτων.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει ένα μόνο όνομα: μια ακολουθία μεταξύ 1 και 3000 (κλειστό διάστημα) κεφαλαίων αγγλικών γραμμάτων. Τα ονόματα είναι διακριτά και δεν δίνονται με ιδιαίτερη σειρά.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο αριθμό πιθανών λιστών κατάταξης, modulo ~1\,000\,000\,007~.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις συνολικής αξίας 60 πόντων, ο αριθμός ~N~ θα είναι μικρότερος από 10.

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

input

3
IVO
JASNA
JOSIPA

output

4

input

5
MARICA
MARTA
MATO
MARA
MARTINA

output

24

input

 4
 A
 AA
 AAA
 AAAA

output

8