Palacinke

Η Άννα έχει καλέσει μερικούς συμμαθητές της για κρέπες (γνωστές ως palačinke στην Κροατία). Έρχονται σε ~T~ λεπτά, και η Άννα μόλις ανακάλυψε ότι δεν έχει κανένα από τα τέσσερα απαραίτητα υλικά (αλεύρι, γάλα, αυγά και μαρμελάδα) που χρειάζεται. Μπαίνει γρήγορα στο αυτοκίνητό της και οδηγεί τριγύρω στη γειτονιά της αγοράζοντας προμήθειες. Η γειτονιά της περιέχει ~N~ διασταυρώσεις αριθμημένες από ~1~ έως ~N~ και ~M~ μονόδρομους που τις συνδέουν. Η Άννα ξεκινά από το σταυροδρόμι ~1~. Σε κάθε δρόμο υπάρχει ακριβώς ένα κατάστημα, που πουλάει μερικά, ή και όλα τα απαραίτητα συστατικά. Η Άννα χρειάζεται ~1~ λεπτό για να οδηγήσει οποιονδήποτε δρόμο, αν δεν σταματήσει στο κατάστημά του και ~2~ λεπτά αν το κάνει. Πρέπει να συγκεντρώσει όλα τα συστατικά και να επιστρέψει πίσω στο σταυροδρόμι 1 στην ώρα της. Της αρέσει να συγκρίνει τις τιμές των καταστημάτων οπότε μπορεί να μπει σε ένα κατάστημα ακόμα έχει ήδη όλα τα συστατικά. Λάβετε υπ'όψιν σας το ακόλουθο παράδειγμα με ~5~ διασταυρώσεις και ~7~ μονόδρομους.

Η Άννα μπορεί να κάνει το δρομολόγιο για τα συστατικά με 5 διαφορετικούς τρόπους, όπως φαίνεται στον παρακάτω πίνακα.

Γράψτε ένα πρόγραμμα που θα υπολογίζει τον αριθμό των διαφορετικών τρόπων με τους οποίους η Άννα μπορεί να αγοράσει τα συστατικά και να επιστρέψει στο σπίτι σε ~T~ λεπτά ή λιγότερο. Επειδή αυτός ο αριθμός μπορεί να είναι πολύ μεγάλος, εκτυπώστε τον το modulo 5557.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους: τον αριθμό απο σταυροδρόμια ~N~ , και τον αριθμό από μονόδρομους ~M~ ~(1 \le N \le 25,\; 1 \le M \le 500)~. Κάθε μία από τις επόμενες ~M~ γραμμές περιέχει δύο διαφορετικούς ακέραιους ~u~ και ~v~ και μια συμβολοσειρά ~s~, χωρισμένα από ένα κενό διάστημα. Περιγράφουν έναν δρόμο που συνδέει τα σταυροδρόμια ~u~ και ~v~, και το κατάστημα που βρίσκεται στο δρόμο και πωλεί υλικά ~s~. Η συμβολοσειρά ~s~ θα περιέχει από ~1~ έως ~4~ κεφαλαίους χαρακτήρες. Χαρακτήρας ~B~ για το αλεύρι, ~J~ για τα αυγά, ~M~ για το γάλα και ~P~ για τη μαρμελάδα. Υπάρχουν το πολύ δύο απευθείας δρόμοι μεταξύ δύο διασταυρώσεων, και μόνο εάν είναι σε αντίθετες κατευθύνσεις. Η τελευταία γραμμή περιέχει έναν ακέραιο αριθμό ~T\;(1 \le T \le 1\,000\,000\,000)~,τον χρόνο μέχρι την άφιξη των φίλων της Άννας, σε λεπτά.

Έξοδος

Η πρώτη και μοναδική γραμμή πρέπει να περιέχει τον αριθμό των διαφορετικών τρόπων με τους οποίους μπορεί η Άννα να αγοράσει τα συστατικά, modulo 5557.

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

input

3 3
1 2 BMJ
2 3 MJP
3 1 JPB
5

output

3

input

3 4
1 2 B
2 1 P
1 3 J
3 1 M
8

output

2

input

5 7
1 2 B
2 4 M
1 3 J
3 4 MB
4 1 JP
4 5 J
5 1 P
7

output

5