Kamion

Ο Mirko είναι οδηγός φορτηγού. Η δουλειά του είναι να ταξιδεύει μεταξύ πόλεων οδικώς, φορτώνοντας και ξεφορτώνοντας το φορτίο. Το φορτηγό του είναι τόσο μεγάλο που μπορεί να φορτώσει απεριόριστο αριθμό δεμάτων, αλλά το αυτοματοποιημένο σύστημα φόρτωσης επιτρέπει την εκφόρτωση μόνο του τελευταίου φορτωμένου πακέτου. Υπάρχουν 26 διαφορετικοί τύποι πακέτων, καθένα από τα οποία συμβολίζεται με ένα γράμμα του αγγλικού αλφαβήτου.

Οι πόλεις συνδέονται με μονόδρομους δρόμους μήκους 1 χιλιομέτρου. Πιο συγκεκριμένα, υπάρχουν ~3~ τύποι των δρόμων, που συμβολίζονται βολικά με τα ~1~, ~2~ και ~3~:

• Τύπος ~1~ - κάθε φορά που ο Mirko οδηγεί στο δρόμο αυτού του τύπου, πρέπει να φορτώσει ακριβώς ένα πακέτο του κατάλληλου τύπου για τον συγκεκριμένο δρόμο
• Τύπος ~2~ - κάθε φορά που ο Mirko οδηγεί στο δρόμο αυτού του τύπου, πρέπει να ξεφορτώσει ακριβώς ένα πακέτο του κατάλληλου τύπου για τον συγκεκριμένο δρόμο
• Τύπος ~3~ - Ο Mirko μπορεί να οδηγήσει στο δρόμο αυτού του τύπου χωρίς να φορτώσει ή να ξεφορτώσει πακέτα (απαγορεύεται η φόρτωση/εκφόρτωση)

Η Mirko υποχρεούται να μην φορτώνει/ξεφορτώνει κανένα φορτίο εκτός από όταν οδηγεί σε δρόμους τύπου ~1~ ή ~2~, όπως αναφέρεται παραπάνω.

Ο Mirko μπορεί να ταξιδέψει κατά μήκος των δρόμων ~E~ που συνδέουν ~N~ πόλεις. Οι εκκινήσεις του στην πόλη σημειώνονται με τον αριθμό ~1~ και ο στόχος του στόχος είναι να φτάσει στην πόλη που συμβολίζεται με τον αριθμό ~N~. Όταν φτάσετε στην πόλη με αριθμό ~N~, το φορτηγό του Mirko δεν απαιτείται να είναι κενό.

Γράψτε ένα πρόγραμμα που να υπολογίζει τον αριθμό των διαφορετικών τρόπων με τους οποίους μπορεί να ταξιδέψει ο Mirko έτσι ώστε να είναι διασχίσει το πολύ ~K~ χιλιόμετρα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει θετικούς ακέραιους ~N~, ~E~ και ~K~ ~(2 \le N \le 50,\,1 \le E \le 2450,\,1 \le K \le 50)~, που δηλώνουν τον αριθμό των πόλεων, τον αριθμό των δρόμων και τον μέγιστο αριθμό χιλιομέτρων που o Mirko μπορεί να διασχίσει πριν φτάσει στον προορισμό του.

Οι ακόλουθες γραμμές ~E~ περιέχουν την περιγραφή των δρόμων κατά μήκος των οποίων μπορεί να ταξιδέψει ο Mirko. Κάθε τύπος δρόμοy έχει τη δική του μορφή:

Τύπος ~1~ – "x y C", όπου ~x~ και ~y~ είναι θετικοί ακέραιοι αριθμοί που περιγράφουν την κατεύθυνση του δρόμου και το ~C~ είναι ένα κεφαλαίο γράμμα του αγγλικού αλφαβήτου που υποδηλώνει τον τύπο συσκευασίας που πρέπει να φορτώσει ο Mirko στο φορτηγό.
Τύπος ~2~ – "x y c", όπου ~x~ και ~y~ είναι θετικοί ακέραιοι αριθμοί που περιγράφουν την κατεύθυνση του δρόμου και το ~c~ είναι ένα πεζό γράμμα του αγγλικού αλφαβήτου που υποδηλώνει τον τύπο συσκευασίας που πρέπει να ξεφορτώσει ο Mirko από το φορτηγό.
Τύπος 3 – "x y", όπου ~x~ και ~y~ είναι θετικοί ακέραιοι αριθμοί που περιγράφουν την κατεύθυνση του δρόμου
Στις παραπάνω μορφές, ο δρόμος είναι διασχίσιμος όταν ταξιδεύετε από την πόλη που συμβολίζεται με ~x~ στην πόλη συμβολίζεται με ~y~. Επίσης, θα ισχύει πάντα ότι ~1 \le x,\,y \le N,\,x \neq y~, και κανένας δρόμος δεν θα συνδέει δύο πόλεις με την ίδια κατεύθυνση.

Έξοδος

Σε μία μόνο γραμμή εξόδου, εκτυπώστε τον αριθμό των διαφορετικών τρόπων με τους οποίους μπορεί να φτάσει ο Mirko στην πόλη με αριθμό ~N~, ξεκινώντας από την πόλη με αριθμό ~1~, τηρώντας τις προαναφερθείσες απαιτήσεις. Επειδή αυτός ο αριθμός μπορεί να είναι αρκετά μεγάλος, εκτυπώστε το υπόλοιπο αυτού του αριθμού όταν διαιρεθεί με το ~10007~.

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

input

2 1 10
1 2 a

output

0

input

7 9 5
1 2 A
2 3 B
2 5
5 3 C
3 4 b
3 6 c
3 7
4 7 a
6 7 a

output

4