Trener

Σε αυτό το σημείο γνωρίζουμε ήδη ότι οι μαθητές αγαπούν να κοιμούνται. Ο Patrik είναι κάτοχος ρεκόρ σε αυτή την κατηγορία. Ξυπνά μόνο όταν χρειάζεται να φάει ή αν επιθυμεί να παίξει FIFA 20. Επομένως, τα όνειρά του συνήθως περιστρέφονται γύρω από το ποδόσφαιρο. Στο τελευταίο του όνειρο βρέθηκε σε ρόλο του προπονητή της αγαπημένης του ομάδας – GNK Dinamo Zagreb.

Η δουλειά του είναι να επιλέξει ~N~ παίκτες που θα παίξουν στην επόμενη σεζόν, αλλά το διοικητικό συμβούλιο έχει κάποια περίεργα αιτήματα. Αυτά είναι:

• Όλοι οι παίκτες πρέπει να έχουν επώνυμα διαφορετικού μήκους.
• Το επώνυμο ενός παίκτη πρέπει να εμφανίζεται ως συνεχής υποακολουθία των επωνύμων όλων των παικτών των οποίων τα επώνυμα είναι μεγαλύτερα.

Για να διευκολύνει τη δουλειά του, ο Patrik μοίρασε τους πιθανούς παίκτες σε ~N~ κουβάδες έτσι ώστε οι παίκτες στον i-οστό κουβά έχουν ακριβώς ~i~ γράμματα στο επώνυμό τους. Σε κάθε έναν από αυτούς τους κουβάδες υπάρχουν ακριβώς ~K~ παίκτες. Ο Patrik θέλει να γνωρίζει με πόσους διαφορετικούς τρόπους (υπόλοιπο ακέραιας διαίρεσης με το ~10^9+ 7~), μπορεί να επιλέξει τους παίκτες για την ομάδα του ενώ επίσης να ανταποκρίνεται στα δεδοµένα αιτήµατα.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N\;(1 \le N \le 50)~ και ~K\;(1 \le K \le 1500)~.
Κάθε μία από τις επόμενες ~N~ γραμμές περιέχει ~K~ (όχι απαραίτητα διακριτά) επώνυμα παικτών. Τα επώνυμα των παικτών, στην i-οστή από αυτές τις γραμμές, αποτελούνται ακριβώς από ~i~ πεζά γράμματα από το αγγλικό αλφάβητο.

Έξοδος

Στη μοναδική γραμμή θα πρέπει να τυπώσετε την απάντηση που ζητήθηκε στην παραπάνω εργασία.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	22	~N = 5~ και ~K = 10~
2	33	~N = 50~ και ~K = 100~
3	55	Κανένας επιπλέον περιορισμός.

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

input

3 2
a b
ab bd
abc abd

output

5

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

Ο Patrik μπορεί να επιλέξει τις ακόλουθες ομάδες: ~(a, ab, abc),\;(a, ab,abd),\;(b, ab, abc),\;(b, ab, abd)~ και ~(b, bd, abd)~.

input

3 3
a b c
aa ab ac
aaa aab aca

output

6

input

3 1
a
bc
def

output

0